Что Вы думаеате о эквивалентности P=NP?

Я думаю, что они очевидно неэквивалентны.

Проще всего взять разницу между детерминированной и недетерминированной машиной тьюринга(или другим автоматом).

Недетерминированная машина с помощью «подкидывания монетки»(недетерминированного перехода) может не вычислять все возможные состояния(а значит и такты), ей может повезти, и она окажется на решении ранее, нежели она переберет все возможные ходы. Для детерминированной машины необходимо вычислить все ветви, а соответственно, мы получаем разницу между ворзможностью везения(и соответственно уменьшения числа тактов) и полным перебором.
Иными словами, стандартный случай для детерминированной машины будет наихудшим случаем для недетерминированной.
Отсюда вытекает неэквивалентность

математика

sortarray sortarray

sortarray

14 896

с 10 января 2016

21 Комментарий

vito333
08 июня 2019, 17:05
сайтом ошибся, бро!
+2
- sortarray sortarray
  08 июня 2019, 17:08
  vito333, тут многие математику любят:)
  0
  - Glago
    08 июня 2019, 18:46
    sortarray sortarray, ммм я бы сказал интересуются, сам не очень её люблю, но чтение смартлаба дало мне в плане математики больше, чем 6 лет бауманки
    +1
Seroja
08 июня 2019, 17:42
Я думаю N=1
0
Михаил
08 июня 2019, 18:16
Докажите и получите больше, чем средний участник сайта на трейдинге
+1
Пафос Респектыч
08 июня 2019, 19:15
Я думаю, что они очевидно неэквивалентны.

Проще всего взять разницу между детерминированной и недетерминированной машиной тьюринга(или другим автоматом).

Где-то здесь логический разрыв ))
0
meat
08 июня 2019, 19:20
это ты так привел доказательство неравенства P и NP или о чем речь?
0
- sortarray sortarray
  08 июня 2019, 19:24
  meat, ну, неформально можно так считать, я думаю.
  Хотелось бы выслушать возможные возражения и указания на ошибки, возможно я не верно понимаю проблему
  0
  - meat
    08 июня 2019, 19:37
    sortarray sortarray, а зачем ты сравниваешь эти две машины? нужно решить какую-то NP-полную задачу за полиномиальное время, чтобы доказать равенство, либо доказать что такую задачу невозможно решить за полиномиальное время, в любом случае получишь 1 млн долларов в виде награды :)
    +1
    - sortarray sortarray
      08 июня 2019, 19:43
      meat, потому что NP это задачи выполняемые на недетерминированных машинах
      0
      - meat
        08 июня 2019, 22:56
        sortarray sortarray, а связь со сравнением какая тогда? пока это выглядит как рандомный ответ, который тебе пришел в голову :)
        вообще любую детерменированную машину можно свести к недетерменированной, вопрос только в том насколько эффективно будет работать такой алгоритм при этом преобразовании — вот это и нужно выяснить, а не сами машины — у тебя вообще дано только описание что делает машина
        0
        sortarray sortarray
        09 июня 2019, 00:01
        meat, NP это non-deterministic polynomial. МТ не может выполнить недетерминистский алгоритм. Никакого «сведения» там нет, просто вместо случайно выбранных путей проходятся все возможные
        0
        meat
        09 июня 2019, 11:13
        sortarray sortarray, опять определения приводишь
        0
        sortarray sortarray
        09 июня 2019, 11:17
        meat, говорите конкретно, что Вы хотите сказать. Вашу версию.
        0
        meat
        09 июня 2019, 11:47
        sortarray sortarray, я вас вообще не понимаю, почему вы считаете что машина тьюринга не может выполнить недетерменированный алгоритм и почему нужно находить все возможные пути
        у вас вопрос был про равенство P и NP, но вы нигде не приводите оценку сложности алгоритмов этих двух классов, мне непонятно зачем вы вообще пытаетесь сравнивать работу двух этих машин
        вместо этого вы описываете работу машины и приводите определения,
        со стороны это выглядит не очень, без обид :)
        может вы какой-то вопрос сформулируете?
        0
        sortarray sortarray
        09 июня 2019, 12:02
        meat, это не я считаю, а «считается». Недетерминированный алгоритм выполняется на недетерминированном автомате.
        0
        meat
        09 июня 2019, 12:09
        sortarray sortarray, никто не спорит же, вы ничего не привели нового, всего лишь поток сознания какой-то из определений в энциклопедии
        с таким же успехом можно выкладывать любой термин из википедии и считать, что вы с кем-то спорите
        0
        sortarray sortarray
        09 июня 2019, 12:10
        meat,
        никто не спорит же, вы ничего не привели новог
        
        Что значит никто не спорит? Именно Вы и спорите
        
        почему вы считаете что машина тьюринга не может выполнить недетерменированный алгоритм и почему нужно находить все возможные пути
        
        Или Вы забываете что говорите?
        0
        meat
        09 июня 2019, 12:20
        sortarray sortarray, не вижу, чтобы я тут спорил с чем-то.
        у вас проблема с пониманием, что такое вопросительное предложение? :)
        жалкие попытки вброса каких-то определений и переход от темы разговора — вы просто не знаете, что ответить и пытаетесь флеймить
        0
        sortarray sortarray
        09 июня 2019, 12:06
        meat, при том, разумеется, НМТ может выполнить то же что и МТ, но не наоборот. К примеру, если у нас стоит задача останова на неопределенном результате «или то или это», МТ не сможет это сделать, ее результат всегда детерминирован. Если она остановится, она остановится на строго-определенном результате
        
        «дайте мне фруктовое или шоколадное мороженное» — «нет, только фруктовое»(при фиксированной входной строке).
        0
netbook
08 июня 2019, 23:47
Разница тогда в константе, что не есть разница
0