SMART-LAB
Новый дизайн
Мы делаем деньги на бирже
Информация
Блог им. sortarray
Что Вы думаеате о эквивалентности P=NP?
- 08 июня 2019, 16:56
- |
Я думаю, что они очевидно неэквивалентны.
Проще всего взять разницу между детерминированной и недетерминированной машиной тьюринга(или другим автоматом).
Недетерминированная машина с помощью «подкидывания монетки»(недетерминированного перехода) может не вычислять все возможные состояния(а значит и такты), ей может повезти, и она окажется на решении ранее, нежели она переберет все возможные ходы. Для детерминированной машины необходимо вычислить все ветви, а соответственно, мы получаем разницу между ворзможностью везения(и соответственно уменьшения числа тактов) и полным перебором.
Иными словами, стандартный случай для детерминированной машины будет наихудшим случаем для недетерминированной.
Отсюда вытекает неэквивалентность
Проще всего взять разницу между детерминированной и недетерминированной машиной тьюринга(или другим автоматом).
Недетерминированная машина с помощью «подкидывания монетки»(недетерминированного перехода) может не вычислять все возможные состояния(а значит и такты), ей может повезти, и она окажется на решении ранее, нежели она переберет все возможные ходы. Для детерминированной машины необходимо вычислить все ветви, а соответственно, мы получаем разницу между ворзможностью везения(и соответственно уменьшения числа тактов) и полным перебором.
Иными словами, стандартный случай для детерминированной машины будет наихудшим случаем для недетерминированной.
Отсюда вытекает неэквивалентность
2.5К |
Читайте на SMART-LAB:
Совкомфлот: танкеры сошли с якоря - текущий год будет ЛУЧШЕ предыдущего, вопрос насколько и стоит ли покупать акции?
Совкомфлот отчитался за 4-й квартал 2025 года — компания продолжает работать в 0 на операционном уровне (всему виной прощальные SDN санкции...
17:30
Криптоиндустрия как новый финансовый рынок
Криптоиндустрия – совокупность рынков и технологических сервисов, которые напрямую связаны с цифровыми активами, в основе которых лежит технология...
16:29
теги блога sortarray sortarray
- It
- smart-lab
- австрийская школа
- акции
- алготрейдинг
- банки
- безработица
- бизнес
- блокчейн
- бухгалтерия
- бюджет
- валюта
- валюты
- ВВП
- веселье
- вопрос
- газпром
- германия
- Глазьев
- деньги
- деривативы
- долг
- долг америки
- долги
- доллар
- ЗОЖ
- золото
- иена
- импортозамещение
- инвестирование
- инвестиции
- инфляция
- история
- капитал
- капитализм
- Катасонов
- кейнс
- Керри Трейд
- керри-трейд
- китай
- коммунизм
- конкуренция
- коронавирус
- короновирус
- кредит
- кризис
- криптовалюта
- криптовалюты
- Кудрин
- либерастия головного мозга
- маркс
- марксизм
- математика
- медведев
- минфин
- налоги
- наука
- нефть
- Облигации
- опционы
- ОФЗ
- оффтоп
- политика
- политэкономия
- право
- Программирование
- психология
- пузырь
- риски
- рубль
- рынок
- рынок труда
- санкции
- собственность
- социализм
- спекуляции
- спорт
- срочный рынок
- СССР
- страхование
- сша
- сырье
- тесла
- теханализ
- торговля
- трейдинг
- украина
- философия
- финансы
- фрс
- фьючерс
- фьючерсы
- ЦБ
- Центробанк
- экономика
- экономика России
- экономика СССР
- эмиссия
- юмор
- юриспруденция
Где-то здесь логический разрыв ))
Хотелось бы выслушать возможные возражения и указания на ошибки, возможно я не верно понимаю проблему
вообще любую детерменированную машину можно свести к недетерменированной, вопрос только в том насколько эффективно будет работать такой алгоритм при этом преобразовании — вот это и нужно выяснить, а не сами машины — у тебя вообще дано только описание что делает машина
у вас вопрос был про равенство P и NP, но вы нигде не приводите оценку сложности алгоритмов этих двух классов, мне непонятно зачем вы вообще пытаетесь сравнивать работу двух этих машин
вместо этого вы описываете работу машины и приводите определения,
со стороны это выглядит не очень, без обид :)
может вы какой-то вопрос сформулируете?
с таким же успехом можно выкладывать любой термин из википедии и считать, что вы с кем-то спорите
Что значит никто не спорит? Именно Вы и спорите
Или Вы забываете что говорите?
у вас проблема с пониманием, что такое вопросительное предложение? :)
жалкие попытки вброса каких-то определений и переход от темы разговора — вы просто не знаете, что ответить и пытаетесь флеймить
«дайте мне фруктовое или шоколадное мороженное» — «нет, только фруктовое»(при фиксированной входной строке).