08 июня 2019, 16:56
Что Вы думаеате о эквивалентности P=NP?
Я думаю, что они очевидно неэквивалентны.
Проще всего взять разницу между детерминированной и недетерминированной машиной тьюринга(или другим автоматом).
Недетерминированная машина с помощью «подкидывания монетки»(недетерминированного перехода) может не вычислять все возможные состояния(а значит и такты), ей может повезти, и она окажется на решении ранее, нежели она переберет все возможные ходы. Для детерминированной машины необходимо вычислить все ветви, а соответственно, мы получаем разницу между ворзможностью везения(и соответственно уменьшения числа тактов) и полным перебором.
Иными словами, стандартный случай для детерминированной машины будет наихудшим случаем для недетерминированной.
Отсюда вытекает неэквивалентность
Проще всего взять разницу между детерминированной и недетерминированной машиной тьюринга(или другим автоматом).
Недетерминированная машина с помощью «подкидывания монетки»(недетерминированного перехода) может не вычислять все возможные состояния(а значит и такты), ей может повезти, и она окажется на решении ранее, нежели она переберет все возможные ходы. Для детерминированной машины необходимо вычислить все ветви, а соответственно, мы получаем разницу между ворзможностью везения(и соответственно уменьшения числа тактов) и полным перебором.
Иными словами, стандартный случай для детерминированной машины будет наихудшим случаем для недетерминированной.
Отсюда вытекает неэквивалентность
Читайте на SMART-LAB:
GBP/USD: Звездный час продавцов — приговор бычьим надеждам
Британский фунт завершил пятничные торги формированием паттерна «падающая звезда», четко оттолкнувшись от точки пересечения ключевых технических линий. Сопротивление здесь носит комплексный...
19.04.2026
ПАО «МГКЛ» получило международный кредитный рейтинг
Компания стала первым российским эмитентом, которому в Индии присвоен кредитный рейтинг в национальной валюте по международной шкале ПАО «МГКЛ» получило долгосрочный кредитный рейтинг по...
17.04.2026
Операционные результаты ПАО «АПРИ» за 1 квартал 2026 года: увеличение объёма продаж почти в 3 раза
Операционные результаты ПАО «АПРИ» за 1 квартал 2026 года: увеличение объёма продаж почти в 3 раза
Объём продаж в 1 квартале 2026 года вырос в 2,8 раз г/г и составил 40,29 тыс....
17.04.2026
Завтра/сегодня ещё напишите, что вы там за ночь надумали — за космос, ИИ в этом космосе и неандертальцах!
Иванов Эдуард, у них выручка основная — оптовая торговля топливом. АЗС дают слезы
khornickjaadle, не совсем понял, какое отношение имеют «газовой станции и электроэнергия..» к банановым плантациям. Но «выручку 100 млн. прогнозируют.» интересно звучит, ещё бы ссылку на отчёт по э...
Алексей Зайцев, святая троица Теперь понятно куда делись 1,2 ярда запасов, превратились в 15 генераторов которые сами же и купили за 1,5 ляма, это магиявсе запасы ушли через другую фирму, а этот (у...
Золото нефть серебро При текущей волатильности туда-сюда можно забыть про все остальные инструменты. Даже про форекс. Акциями торгуют как раз чтобы заработать денег на сильных движениях, ну а фьючерсы...
Золото нефть серебро При текущей волатильности туда-сюда можно забыть про все остальные инструменты. Даже про форекс. Акциями торгуют как раз чтобы заработать денег на сильных движениях, ну а фьючерсы...
Взялся за гуж, не говори, что не дюж Мне очень доходчиво объяснили, что бы я заканчивал свой альтруизм и аргументы показались мне весьма и весьма убедительными.
Я извинился за предыдущий свой про...
Как не получить штраф по 3-НДФЛ и успеть подать всё вовремя в 2026 году Практическая инструкция для инвестора с зарубежными счетами
Апрель — самый ответственный месяц для частного инвестора...
YgrOK, процесс бреет латышей. Вообще ничего не поменяется от этого процесса в целом. 13,2 млрд потенциал списания марьино. Одновременно с этим 10-12 млрд сокращения фин расходов на снижении ставки....
Новые облигации Селигдар: 16,5% сбор сегодня, 20.04
A+/AA-, купон др 16,5% ежемес. (YTM до 17,81%), 3 года, 2 млрд.Бумага из категории соблазнительных, но небезопасных эмитентов, выходящих до ра...
Где-то здесь логический разрыв ))
Хотелось бы выслушать возможные возражения и указания на ошибки, возможно я не верно понимаю проблему
вообще любую детерменированную машину можно свести к недетерменированной, вопрос только в том насколько эффективно будет работать такой алгоритм при этом преобразовании — вот это и нужно выяснить, а не сами машины — у тебя вообще дано только описание что делает машина
у вас вопрос был про равенство P и NP, но вы нигде не приводите оценку сложности алгоритмов этих двух классов, мне непонятно зачем вы вообще пытаетесь сравнивать работу двух этих машин
вместо этого вы описываете работу машины и приводите определения,
со стороны это выглядит не очень, без обид :)
может вы какой-то вопрос сформулируете?
с таким же успехом можно выкладывать любой термин из википедии и считать, что вы с кем-то спорите
Что значит никто не спорит? Именно Вы и спорите
Или Вы забываете что говорите?
у вас проблема с пониманием, что такое вопросительное предложение? :)
жалкие попытки вброса каких-то определений и переход от темы разговора — вы просто не знаете, что ответить и пытаетесь флеймить
«дайте мне фруктовое или шоколадное мороженное» — «нет, только фруктовое»(при фиксированной входной строке).