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

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

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

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

математика

sortarray sortarray

sortarray

14 896

с 10 января 2016

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

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

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

Где-то здесь логический разрыв ))
0

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

Не оливье единым: итоги 2025 года и новая иерархия на рынке готовых салатов

Российский рынок готовых салатов в 2025 году продемонстрировал смену лидера: традиционный фаворит «Оливье» уступил первое место «Сельди под шубой», показав при этом самое значительное подорожание...

Газпромбанк

11:54

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

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

МГКЛ

10:00

Возобновляем сбор вопросов для предстоящего интервью с Л-Стартом

Эфир с Дмитрием Смирновым запланирован на следующей неделе и сейчас есть отличная возможность напрямую задать интересующие вас вопросы о компании ее бенефициару. Вопросы можете направлять в...