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

✅ ПАО «МГКЛ» завершило размещение второго выпуска облигаций на СПБ Бирже

ПАО «МГКЛ» успешно завершило размещение биржевых облигаций серии 001PS-02 на СПБ Бирже объёмом 1 млрд рублей. Выпуск был размещён в полном объёме. 📌 Итоговые параметры выпуска: 🟠 ставка...

МГКЛ

06.03.2026

Обновление кредитных рейтингов в ВДО и розничных облигациях (ПАО «ЕВРОТРАНС» присвоен статус "Под наблюдением", ПАО «ГК «САМОЛЕТ» снят статус "Под наблюдением")

⚪️ПАО «ЕвроТранс» Эксперт РА установил статус «под наблюдением» по рейтингу кредитоспособности, что означает высокую вероятность рейтинговых действий в ближайшее время. Рейтинг компании...

Иволга Капитал

09:00

💻 Хватит гуглить про недопустимые события

Мы часто говорим о недопустимых событиях. Только в этом канале упоминали их в 42 (!) постах за последние несколько лет. И каждый раз старались объяснить вам, что это такое. Например, как-то...

Positive Technologies

06.03.2026

Нефтяной срез: выпуск №8. Перекрытие Ормузского пролива + рост цен на нефть против слабых отчетов за 4-й квартал 2025 и 1-й квартал 2026? Ищем лучших в все еще слабом секторе

Продолжаю выпускать рубрику — Нефтяной срез. Цель: отслеживать важные бенчмарки в нефтяной отрасли, чтобы понимать куда дует ветер. Прошлый пост: smart-lab.ru/mobile/topic/1229385/ Почему...