Что Вы думаеате о эквивалентности 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

Читайте на SMART-LAB:

5 идей в российских акциях. Индекс МосБиржи снова на грани 2700

Индекс МосБиржи опять торгуется на грани значимого уровня 2700 п. Сейчас не исключен очередной отскок от указанного уровня. Кроме того, рынок находится на 12% ниже пятимесячного максимума. Это...

БКС Мир инвестиций

08:53

🧠 Ресейл и поколение Z: почему молодёжь выбирает разумное потребление

📱 Поколение Z относится к потреблению прагматичнее, чем остальные. Для них важны не громкие слова и статус, а понятная ценность покупки — сколько она стоит, как долго прослужит и насколько...

МГКЛ

10:00

Промышленная автоматизация — один из ключевых трендов 2026 в ИТ #SOFL_тренды

Сегодня промышленность все чаще смотрит на ИТ как на инструмент для наращивания мощностей. Для российской экономики отрасль играет ключевую роль, и любое отставание в технологиях отражается как...