Что Вы думаеате о эквивалентности 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 популярных фьючерсов на Мосбирже в январе

Московская биржа опубликовала итоги торгов на срочном рынке FORTS за январь 2026 г. Максимальный практический интерес представляет статистика по наиболее ликвидным контрактам. Рассмотрим...

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

06.02.2026

Самолет комментирует новости

Друзья, привет! 💬 В свете громких заголовков СМИ последних дней мы считаем важным поддерживать открытую коммуникацию. ⚡️ В понедельник утром наш финансовый директор Нина Голубничая и директор...

Самолет

06.02.2026

SMA (Simple Moving Average): как работает индикатор и бесплатный робот для OsEngine. Видео.

Разбираем индикатор SMA (Simple Moving Average) - один из самых старых и самых узнаваемых инструментов технического анализа. В видео: 1) как считается SMA 2) какие сигналы он даёт 3) как...

OsEngine

06.02.2026

Астра купила долю в компании у своего контролирующего акционера😢

В среду 4 февраля на сайте раскрытия вышли сущфакты от Астры о совершении сделки с заинтересованностью. Ссылки на сущфакты: ➡️ сделка с заинтересованностью ➡️ дочка Астры ООО...