Теорема Карпа – Липтона утверждает, что если , то P H разрушается до Σ P 2 . Следовательно, при условии разделения между Σ P 2 и Σ P 3 , никакая N P -полная проблема не будет принадлежать P / p o l y .N P ⊂ P / p o l yNP⊂P/poly\mathsf{NP} \subset \mathsf{P/poly}P...
Решение проблемы CNF-SAT можно описать следующим образом: Вход: булева формула в конъюнктивной нормальной форме.ϕφ\phi Вопрос: существует ли присвоение переменной, которая удовлетворяет ?ϕφ\phi Я рассматриваю несколько различных подходов к решению проблемы CNF-SAT с помощью недетерминированной...
В своей статье (стр. 503) Гарей и Джонсон замечают: ... может существовать NP-полная задача, которая не является NP-полной в строгом смысле и не разрешима алгоритмом псевдополиномиального времени ... Кто-нибудь знает некоторые возможные проблемы со свойствами, упомянутыми выше? Я думаю, что...
Существует ли известный явный пример алгоритма со свойством, состоящим в том, что если то этот алгоритм не выполняется за полиномиальное время, а если то он выполняется за полиномиальное время?п≠ Nпп≠NпP\neq NPп= Nппзнак...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
Parity-P - это набор языков, распознаваемых недетерминированной машиной Тьюринга, которая может различать только четное число или нечетное число путей «принятия» (а не нулевое или ненулевое число путей принятия). Таким образом, Parity-P - это, в основном, младший брат PP с задержкой роста: в то...
Знаменитая гипотеза об изоморфизме Бермана и Хартманиса говорит, что все -полные языки полиномиально по времени изоморфны (p-изоморфны) друг другу. Ключевое значение гипотезы является то , что она предполагает P ≠ N P . Она была опубликована в 1977 году, и часть подтверждающих доказательств, что...
Я думаю, что было бы неплохо составить список теорем, утверждающих, что P не равен NP, если и только если такие и такие выходы существуют, некоторый класс сложности содержится в другом классе сложности и так далее, и так далее....
Я заинтересован в изучении связей между «хаосом» или, в более широком смысле, динамическими системами и вопросом . Вот пример типа литературы, которую я ищу:п= Nппзнак равноNпP{=}NP Эрчи-Раваш, Мария и Золтан Торошкай. «Твердость оптимизации как переходный хаос в аналоговом подходе к удовлетворению...
Сетевой коммутатор (название придумано) выполнен с тремя типами узлов: один начальный узел один конечный узел один или несколько узлов коммутатора Узел коммутатора имеет 3 выхода: влево, вверх, вправо; имеет два состояния L и R и целевое состояние TL или TR . Каждый переключатель может быть пройден...
Пусть 0≤p≤10≤p≤10\le p\le 1 и рассмотрим решение задачи CLIQUE Ввод: целое числоpp_p sss , граф GGG с ttt вершинами и края Вопрос: действительно содержит клику по крайней мере вершинами?⌈p(t2)⌉⌈p(t2)⌉\lceil p\binom{t}{2} \rceil GGGsss Экземпляр CLIQUE содержит пропорцию от всех возможных ребер....
Я читал, что целочисленное линейное программирование разрешимо за полиноминальное время, если число переменных фиксировано, т.е. n ∈ O ( 1 ) . Если число переменных растет логарифмически, т. Е. N ∈ O ( log 2 ( N ) ) для заданного входного значения размера N , проблема все еще разрешима за...
Гауэрс недавно изложил проблему, которую он называет «дискретизированной определенностью Бореля», решение которой связано с доказательством нижних границ схемы. Можете ли вы дать краткое изложение подхода, ориентированного на аудиторию теоретиков сложности? Что потребуется для этого подхода, чтобы...
С чисто абстрактной математической / вычислительной точки зрения (как) можно даже узнать или рассуждать о таких проблемах, как 3-SAT, сумма подмножества, коммивояжер и т. Д.,? Сможем ли мы хоть как-то осмыслить их с функциональной точки зрения? Будет ли это вообще возможно? Я размышлял над этим...
FewP - это класс -задач с полиномиальной оценкой числа решений (во входном размере). Там нет никакого известного Св.нут P -полные проблемы в ф х ш Р . Мне интересно, как далеко мы можем расширить это наблюдение.NпNPNPNпNPNPее ш РfewPfewP Существует ли естественная -полная проблема с...
Мы все знаем, что у есть барьеры. Мы все изучили эти барьеры, потому что мы считаем, что .P ≠ N Pп≠ NпP≠NPP\ne NPп≠ NпP≠NPP\ne NP Однако предположим, что и есть мудрые люди, которые считают, что такая возможность существует . Если это действительно так, то сам факт того, что мы не видели хороших...
В другом посте cstheorySE упоминается, что PSPACE-полнота подразумевает APX-жесткость. Кто-нибудь может объяснить / поделиться ссылкой на это? Это "плотно"? (т. е. существуют ли PSPACE-полные задачи, задача оптимизации которых допускает постоянную аппроксимацию множителя за много времени?) Как...
Существует ли , NP- или P-полный язык, имеющий некоторое семейство групп симметрии (или группоид , но тогда алгоритмические вопросы становятся более открытыми), действующий (за полиномиальное время) на множествах такой, что орбит мало, т. е. такой, что для достаточно больших и некоторого c , и...
Теорема Райса утверждает, что каждое нетривиальное свойство множества, распознаваемое некоторой машиной Тьюринга, неразрешимо. Я ищу теорему о сложности теории Райса, которая говорит нам, какие нетривиальные свойства NP-множеств...
Вот проблема: У нас есть квадрат с несколькими числами от 1..N в некоторых ячейках. Нужно определить, можно ли его завершить до магического квадрата. Примеры: 2 _ 6 2 7 6 _ 5 1 >>> 9 5 1 4 3 _ 4 3 8 7 _ _ 9 _ _ >>> NO SOLUTION 8 _ _ Эта проблема NP-полная? Если да, как я могу это...