Насколько я понимаю, доказательство того, что P = NP или P ≠ NP, должно быть нерелятивизируемым (как в оракулах теории рекурсии). Практически все доказательства кажутся релятивизируемыми. Какие хорошие примеры , не являющиеся Релятивизуемых доказательств, из тех , что Р = NP / P ≠ NP доказательству...
Вот проблема: У нас есть квадрат с несколькими числами от 1..N в некоторых ячейках. Нужно определить, можно ли его завершить до магического квадрата. Примеры: 2 _ 6 2 7 6 _ 5 1 >>> 9 5 1 4 3 _ 4 3 8 7 _ _ 9 _ _ >>> NO SOLUTION 8 _ _ Эта проблема NP-полная? Если да, как я могу это...
Вопрос возник у меня, когда я получил ответ Даны Мошковиц на другую тему . Пусть будет языком NP , и пусть будет соответствующим отношением NP . Мы знаем, что существует некоторый полином такой, что:LLLрLрLR_Lппp ∀ x ∈ L ,, ∃ ж ∈0 , 1р ( | х | )( x , w ) ∈...
Свойство графа называется наследственным, если оно замкнуто относительно удаления вершин (т. Е. Все индуцированные подграфы наследуют это свойство). Свойство графа называется аддитивным, если оно замкнуто относительно взятия непересекающихся объединений. Нетрудно найти свойства, которые являются...
В этой лекционной заметке Олы Свенссон: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf говорится, что мы не знаем, находится ли евклидова TSP в NP: Причина в том, что мы не знаем, как эффективно рассчитать квадратные корни. С другой стороны, есть документ Пападимитриу:...
Мне недавно напомнили о проблеме против N P, как объяснил Стивен А. Кук в Математическом институте Клея.пP\mathsf{P}Н ПNP\mathsf{NP} Это вызвало у меня интерес, и я хотел бы узнать об этом больше. Первым шагом будет более глубокое понимание проблемы и понимание области в целом. Можете ли вы...
ETH утверждает, что SAT не может быть решена в худшем случае за субэкспоненциальное время. Как насчет среднего случая? Есть ли естественные проблемы в NP, которые предположительно будут экспоненциально сложными в среднем случае? Возьмите средний случай, чтобы означать среднее время работы с...
Что меня особенно интересует, так это наличие интересного условия о проценте назначений, которые удовлетворяют формуле 3SAT, чтобы гарантировать, что такие проблемы поддаются решению. Предположим, например, класс задач 3SAT, что из возможных назначений удовлетворяет булевой формуле; мы можем...
в 1979 году Хопкрофт / Ульман написал, что L ⊆ P ⊆ NP ⊆ PSpace известно, но L ⊊ PSpace является единственным известным (и тривиальным) сдерживанием, известным, хотя все предполагаются как надлежащие сдерживания, и «где вещи все еще стоят» ~ 4 десятилетия спустя , с тех пор существует ли какая-либо...
Зафиксируем NP-полную задачу поиска, например форму поиска SAT. Поиск Левина предоставляет алгоритм L для решения X, который в некотором смысле является оптимальным. В частности, алгоритм таков: «Выполните все возможные программы P в соответствии друг с другом на входе x , как только некоторые P...
Я совершенно уверен, что я не первый, кто принимает идею, которую я собираюсь представить. Однако было бы полезно, если бы я мог найти какую-либо литературу, связанную с этой идеей. Идея состоит в том, чтобы построить машину Тьюринга M со свойством, что если P = NP, то M будет решать 3-SAT за...
Существуют ли NP-полные (или даже NP-сложные, или NP) задачи, которые имеют хорошие топологические свойства для изучения. Есть ли у задач NP теоретические формулировки узлов? Мы знаем о результатах # о полиноме Джонса. Графические задачи (вложения?), В частности раскраски графов, могут иметь...
Следующий вопрос использует идеи из криптографии, примененные к теории сложности. Тем не менее, это чисто теоретический вопрос сложности, и для его ответа не требуется никаких криптовалют. Я намеренно пишу этот вопрос очень неформально. В отсутствие подробностей, это, возможно, указано немного...
Рассмотрим полную информацию о комбинаторных играх для двух игроков, которые заканчиваются после полиномиального числа ходов, и поочередно игроки выбирают из конечного числа разрешенных ходов. Обычный вопрос в том, насколько сложно с определенной позиции отличить победителя. Другой будет, как...
Меня интересует вопрос, является ли NP равным coNP или нет. Я был бы очень признателен за советы о хороших публикациях по этой теме. Для справки, я знаю, что этот вопрос тесно связан с вопросом о том, равен ли P NP или нет (например, если NP! = CoNP, то P! = NP). Ура,...
Предположим, что NP = co-NP, а полином ограничивает длину доказательства неудовлетворенности для экземпляра 3-CNF x . Тогда есть ли какие-либо результаты о том, в какой форме может быть получено любое доказательство неудовлетворенности для x длины ≤ p ( x ) ? Т.е. в целом, должно ли такое...
В статье Стивена Кука о проблеме P против NP [1] он утверждает следующее [2]: Тезис осуществимости: естественная задача имеет выполнимый алгоритм, если он имеет алгоритм полиномиального времени. У меня вопрос, что именно он (или вообще, на самом деле, что один) подразумевает под « естественной...
Прежде всего, мое понимание теоремы Гёделя о неполноте (и формальной логики в целом) очень наивно, а также мои знания в области теоретической информатики (имеется в виду только один выпускной курс, когда я еще студент), поэтому этот вопрос может быть очень наивно Насколько я мог найти, доказуемость...
Доказательство сложности является основной областью теории вычислительной сложности. Конечная цель этой области состоит в том, чтобы доказать , то есть любой доказатель не может дать доказательство неудовлетворенности данной входной формулой. Nп≠ c o NпNп≠соNпNP\neq coNP Граф - это одна из...
Хорошо известно , что некоторые классы NP -проблемы Have дихотомии теорем, которые гарантируют , что каждая задача в классе является либо NP -полное или находится в P . Наиболее известным таким результатом является теорема Шефера о дихотомии , а также ряд обобщений. Насколько я понимаю, доказать...