15
ответов

На что доказательство P=NP было бы похоже, гипотетически?

Это был бы полиномиальный алгоритм времени к определенной полной NP проблеме или просто абстрактные обоснования, которые демонстрируют, решения полных NP проблем существуют? Кажется что определенный algoithm...
вопрос задан: 16 February 2010 17:59
7
ответов

Объясните доказательство Виная Деолаликар, что P! = NP [закрыто]

Недавно в лаборатории HP в Vinay Deolalikar появилась информация о том, что P! = NP. Может ли кто-нибудь объяснить, как это доказательство работает для нас менее математически ...
вопрос задан: 13 April 2017 14:17
6
ответов

Что отсутствует для этого P! = доказательство NP?

Я пытался восстановить пароль. При размышлении об этом я распознал, что проблемой "восстановление пароля" является очень хороший пример проблемы NP. Если Вы знаете пароль, очень легко проверить его в...
вопрос задан: 12 March 2010 09:09
6
ответов

Что такое “P=NP?”, и почему это - такой известный вопрос? [закрытый]

Вопрос того, является ли P=NP, возможно, самым известным во всей Информатике.Что это значит? И почему это настолько интересно? О, и для дополнительного кредита, отправьте доказательство оператора...
вопрос задан: 18 February 2010 01:45
1
ответ

P=NP: Каковы самые многообещающие методы?

Я знаю, что P=NP не был решен до сих пор, но может кто-либо говорить мне что-то о следующем: Что в настоящее время является самым многообещающим математическим / компьютер научные методы, которые могли быть...
вопрос задан: 8 December 2013 19:03
0
ответов

«Поиск всего кода в заданном двоичном файле эквивалентен проблеме остановки». В самом деле?

Я только что прочитал получивший большое количество голосов вопрос относительно эмуляторов и утверждение. Было доказано, что поиск всего кода в заданном двоичном файле эквивалентен проблеме остановки. На самом деле ...
вопрос задан: 23 May 2017 10:24
0
ответов

NP-сложные задачи, которые не являются NP-полными, сложнее?

Насколько я понимаю, все NP-полные проблемы являются NP-сложными, но некоторые NP -сложные задачи, как известно, не являются NP-полными, а NP-сложные задачи по крайней мере так же сложны, как NP-полные проблемы. Означает ли это ...
вопрос задан: 28 September 2010 05:26
0
ответов

Почему проблемы NP называются именно так (а также NP-hard и NP-complete) ?

В самом деле ... Во вторник у меня последний экзамен на выпускной, и это одна из вещей, которую я никогда не мог понять. Я понимаю, что решение проблемы NP можно проверить за полиномиальное время. ...
вопрос задан: 8 September 2010 20:00