SMART-LAB
Новый дизайн
Мы делаем деньги на бирже
Информация
Блог им. sortarray
Что Вы думаеате о эквивалентности P=NP?
- 08 июня 2019, 16:56
- |
Я думаю, что они очевидно неэквивалентны.
Проще всего взять разницу между детерминированной и недетерминированной машиной тьюринга(или другим автоматом).
Недетерминированная машина с помощью «подкидывания монетки»(недетерминированного перехода) может не вычислять все возможные состояния(а значит и такты), ей может повезти, и она окажется на решении ранее, нежели она переберет все возможные ходы. Для детерминированной машины необходимо вычислить все ветви, а соответственно, мы получаем разницу между ворзможностью везения(и соответственно уменьшения числа тактов) и полным перебором.
Иными словами, стандартный случай для детерминированной машины будет наихудшим случаем для недетерминированной.
Отсюда вытекает неэквивалентность
Проще всего взять разницу между детерминированной и недетерминированной машиной тьюринга(или другим автоматом).
Недетерминированная машина с помощью «подкидывания монетки»(недетерминированного перехода) может не вычислять все возможные состояния(а значит и такты), ей может повезти, и она окажется на решении ранее, нежели она переберет все возможные ходы. Для детерминированной машины необходимо вычислить все ветви, а соответственно, мы получаем разницу между ворзможностью везения(и соответственно уменьшения числа тактов) и полным перебором.
Иными словами, стандартный случай для детерминированной машины будет наихудшим случаем для недетерминированной.
Отсюда вытекает неэквивалентность
2.5К |
Читайте на SMART-LAB:
Средние доходности облигаций в зависимости от кредитного рейтинга. От B- до AA+
👉 Наш канал в MAX 👈
👉 Чат Иволги в MAX 👈
Средние доходности облигаций в зависимости от рейтинга (бледные столбцы — доходности...
07:21
👌 Время вспомнить о забытом активе
С начала года российский рынок акций демонстрирует неэластичность к изменению ключевых факторов для оценки.
Индекс Мосбиржи почти не...
12:44
теги блога sortarray sortarray
- It
- smart-lab
- австрийская школа
- акции
- алготрейдинг
- банки
- безработица
- бизнес
- блокчейн
- бухгалтерия
- бюджет
- бюджетная политика
- валюта
- валюты
- ВВП
- веселье
- вопрос
- газпром
- германия
- Глазьев
- госдолг США
- деньги
- деривативы
- долг
- доллар
- доллар йена
- ЗОЖ
- золото
- импортозамещение
- инвестиции
- инфляция
- история
- капитал
- капитализм
- Катасонов
- кейнс
- Керри Трейд
- керри-трейд
- китай
- коммунизм
- конкуренция
- коронавирус
- короновирус
- кредит
- кризис
- криптовалюта
- Кудрин
- либерастия головного мозга
- маркс
- марксизм
- математика
- медведев
- минфин
- налоги
- наука
- нефть
- Облигации
- опционы
- ОФЗ
- оффтоп
- политика
- политэкономия
- право
- Программирование
- процентная ставка
- психология
- пузырь
- риски
- рубль
- рынок
- рынок труда
- санкции
- секьюритизация
- собственность
- социализм
- спекуляции
- спорт
- срочный рынок
- СССР
- страхование
- сша
- сырье
- тесла
- технический анализ
- торговля
- трейдинг
- украина
- философия
- финансы
- ФРС США
- фьючерсы
- ЦБ РФ
- Центробанк
- экономика
- экономика России
- экономика СССР
- эмиссия
- энергетика
- юмор
- юриспруденция
Где-то здесь логический разрыв ))
Хотелось бы выслушать возможные возражения и указания на ошибки, возможно я не верно понимаю проблему
вообще любую детерменированную машину можно свести к недетерменированной, вопрос только в том насколько эффективно будет работать такой алгоритм при этом преобразовании — вот это и нужно выяснить, а не сами машины — у тебя вообще дано только описание что делает машина
у вас вопрос был про равенство P и NP, но вы нигде не приводите оценку сложности алгоритмов этих двух классов, мне непонятно зачем вы вообще пытаетесь сравнивать работу двух этих машин
вместо этого вы описываете работу машины и приводите определения,
со стороны это выглядит не очень, без обид :)
может вы какой-то вопрос сформулируете?
с таким же успехом можно выкладывать любой термин из википедии и считать, что вы с кем-то спорите
Что значит никто не спорит? Именно Вы и спорите
Или Вы забываете что говорите?
у вас проблема с пониманием, что такое вопросительное предложение? :)
жалкие попытки вброса каких-то определений и переход от темы разговора — вы просто не знаете, что ответить и пытаетесь флеймить
«дайте мне фруктовое или шоколадное мороженное» — «нет, только фруктовое»(при фиксированной входной строке).