SMART-LAB
Новый дизайн
Мы делаем деньги на бирже
Информация
Блог им. sortarray
Что Вы думаеате о эквивалентности P=NP?
- 08 июня 2019, 16:56
- |
Я думаю, что они очевидно неэквивалентны.
Проще всего взять разницу между детерминированной и недетерминированной машиной тьюринга(или другим автоматом).
Недетерминированная машина с помощью «подкидывания монетки»(недетерминированного перехода) может не вычислять все возможные состояния(а значит и такты), ей может повезти, и она окажется на решении ранее, нежели она переберет все возможные ходы. Для детерминированной машины необходимо вычислить все ветви, а соответственно, мы получаем разницу между ворзможностью везения(и соответственно уменьшения числа тактов) и полным перебором.
Иными словами, стандартный случай для детерминированной машины будет наихудшим случаем для недетерминированной.
Отсюда вытекает неэквивалентность
Проще всего взять разницу между детерминированной и недетерминированной машиной тьюринга(или другим автоматом).
Недетерминированная машина с помощью «подкидывания монетки»(недетерминированного перехода) может не вычислять все возможные состояния(а значит и такты), ей может повезти, и она окажется на решении ранее, нежели она переберет все возможные ходы. Для детерминированной машины необходимо вычислить все ветви, а соответственно, мы получаем разницу между ворзможностью везения(и соответственно уменьшения числа тактов) и полным перебором.
Иными словами, стандартный случай для детерминированной машины будет наихудшим случаем для недетерминированной.
Отсюда вытекает неэквивалентность
2.5К |
Читайте на SMART-LAB:
Снижаем рейтинг акций ВТБ при сохранении таргета
Котировки группы ВТБ в ходе торгов 16 апреля поднялись на 1,15%, до 94,82 руб. за акцию.Конвертация бумаг банка не приведет к непосредственному...
16 апреля 2026, 19:40
🔥 Займер переходит от «займов до зарплаты» к кредитным лимитам
Финтех-группа «Займер» объявляет операционные результаты I квартала 2026 года. Наибольшая доля выдач за этот период пришлась на новый флагманский...
17 апреля 2026, 09:01
теги блога sortarray sortarray
- It
- smart-lab
- австрийская школа
- акции
- алготрейдинг
- банки
- безработица
- бизнес
- блокчейн
- бухгалтерия
- бюджет
- бюджетная политика
- валюта
- валюты
- ВВП
- веселье
- вопрос
- газпром
- германия
- Глазьев
- госдолг США
- деньги
- деривативы
- долг
- доллар
- доллар йена
- ЗОЖ
- золото
- импортозамещение
- инвестиции
- инфляция
- история
- капитал
- капитализм
- Катасонов
- кейнс
- Керри Трейд
- керри-трейд
- китай
- коммунизм
- конкуренция
- коронавирус
- короновирус
- кредит
- кризис
- криптовалюта
- Кудрин
- либерастия головного мозга
- маркс
- марксизм
- математика
- медведев
- минфин
- налоги
- наука
- нефть
- Облигации
- опционы
- ОФЗ
- оффтоп
- политика
- политэкономия
- право
- Программирование
- процентная ставка
- психология
- пузырь
- риски
- рубль
- рынок
- рынок труда
- санкции
- секьюритизация
- собственность
- социализм
- спекуляции
- спорт
- срочный рынок
- СССР
- страхование
- сша
- сырье
- тесла
- технический анализ
- торговля
- трейдинг
- украина
- философия
- финансы
- ФРС США
- фьючерсы
- ЦБ РФ
- Центробанк
- экономика
- экономика России
- экономика СССР
- эмиссия
- энергетика
- юмор
- юриспруденция
Где-то здесь логический разрыв ))
Хотелось бы выслушать возможные возражения и указания на ошибки, возможно я не верно понимаю проблему
вообще любую детерменированную машину можно свести к недетерменированной, вопрос только в том насколько эффективно будет работать такой алгоритм при этом преобразовании — вот это и нужно выяснить, а не сами машины — у тебя вообще дано только описание что делает машина
у вас вопрос был про равенство P и NP, но вы нигде не приводите оценку сложности алгоритмов этих двух классов, мне непонятно зачем вы вообще пытаетесь сравнивать работу двух этих машин
вместо этого вы описываете работу машины и приводите определения,
со стороны это выглядит не очень, без обид :)
может вы какой-то вопрос сформулируете?
с таким же успехом можно выкладывать любой термин из википедии и считать, что вы с кем-то спорите
Что значит никто не спорит? Именно Вы и спорите
Или Вы забываете что говорите?
у вас проблема с пониманием, что такое вопросительное предложение? :)
жалкие попытки вброса каких-то определений и переход от темы разговора — вы просто не знаете, что ответить и пытаетесь флеймить
«дайте мне фруктовое или шоколадное мороженное» — «нет, только фруктовое»(при фиксированной входной строке).