Блог им. sortarray

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

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

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

Недетерминированная машина с помощью «подкидывания монетки»(недетерминированного перехода) может не вычислять все возможные состояния(а значит и такты), ей может повезти, и она окажется на решении ранее, нежели она переберет все возможные ходы. Для детерминированной машины необходимо вычислить все ветви, а соответственно, мы получаем разницу между ворзможностью везения(и соответственно уменьшения числа тактов) и полным перебором.
Иными словами, стандартный случай для детерминированной машины будет наихудшим случаем для недетерминированной.
Отсюда вытекает неэквивалентность
★2
21 комментарий
сайтом ошибся, бро!
avatar
vito333, тут многие математику любят:)
sortarray sortarray, ммм я бы сказал интересуются, сам не очень её люблю, но чтение смартлаба дало мне в плане математики больше, чем 6 лет бауманки
avatar
Я думаю N=1
avatar
Докажите и получите больше, чем средний участник сайта на трейдинге
avatar
Я думаю, что они очевидно неэквивалентны.

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

Где-то здесь логический разрыв ))
это ты так привел доказательство неравенства P и NP или о чем речь?
avatar
meat, ну, неформально можно так считать, я думаю.
Хотелось бы выслушать возможные возражения и указания на ошибки, возможно я не верно понимаю проблему
sortarray sortarray, а зачем ты сравниваешь эти две машины? нужно решить какую-то NP-полную задачу за полиномиальное время, чтобы доказать равенство, либо доказать что такую задачу невозможно решить за полиномиальное время, в любом случае получишь 1 млн долларов в виде награды :)
avatar
meat, потому что NP это задачи выполняемые на недетерминированных машинах
sortarray sortarray, а связь со сравнением какая тогда? пока это выглядит как рандомный ответ, который тебе пришел в голову :)
вообще любую детерменированную машину можно свести к недетерменированной, вопрос только в том насколько эффективно будет работать такой алгоритм при этом преобразовании — вот это и нужно выяснить, а не сами машины — у тебя вообще дано только описание что делает машина
avatar
meat, NP это non-deterministic polynomial. МТ не может выполнить недетерминистский алгоритм. Никакого «сведения» там нет, просто вместо случайно выбранных путей проходятся все возможные
sortarray sortarray, опять определения приводишь
avatar
meat, говорите конкретно, что Вы хотите сказать. Вашу версию.
sortarray sortarray, я вас вообще не понимаю, почему вы считаете что машина тьюринга не может выполнить недетерменированный алгоритм и почему нужно находить все возможные пути
у вас вопрос был про равенство P и NP, но вы нигде не приводите оценку сложности алгоритмов этих двух классов, мне непонятно зачем вы вообще пытаетесь сравнивать работу двух этих машин
вместо этого вы описываете работу машины и приводите определения,
со стороны это выглядит не очень, без обид :)
может вы какой-то вопрос сформулируете?
avatar
meat, это не я считаю, а «считается». Недетерминированный алгоритм выполняется на недетерминированном автомате.
sortarray sortarray, никто не спорит же, вы ничего не привели нового, всего лишь поток сознания какой-то из определений в энциклопедии
с таким же успехом можно выкладывать любой термин из википедии и считать, что вы с кем-то спорите
avatar
meat,
никто не спорит же, вы ничего не привели новог

 Что значит никто не спорит? Именно Вы и спорите

почему вы считаете что машина тьюринга не может выполнить недетерменированный алгоритм и почему нужно находить все возможные пути

Или Вы забываете что говорите?
sortarray sortarray, не вижу, чтобы я тут спорил с чем-то. 
у вас проблема с пониманием, что такое вопросительное предложение? :)
жалкие попытки вброса каких-то определений и переход от темы разговора — вы просто не знаете, что ответить и пытаетесь флеймить
avatar
meat, при том, разумеется, НМТ может выполнить то же что и МТ, но не наоборот. К примеру, если у нас стоит задача останова на неопределенном результате «или то или это», МТ не сможет это сделать, ее результат всегда детерминирован. Если она остановится, она остановится на строго-определенном результате

«дайте мне фруктовое или шоколадное мороженное» — «нет, только фруктовое»(при фиксированной входной строке).
Разница тогда в константе, что не есть разница
avatar

теги блога sortarray sortarray

....все тэги



UPDONW