Каждый раз, когда я преподаю NP-Полноту, студенты спрашивают: «Есть ли проблемы, о которых известно, что они не относятся к NP?» Как бы вы ответили? Я обычно даю им неразрешимую проблему в качестве примера, но это часто не очень хорошо получается: (а) если я дам им проблему остановки, они думают,...
Этот вопрос мотивирован вопросом MathOverflow Пэна Чжана . Валиант показал, что подсчет максимальных клик в общем графе является # P-полным, но что если мы ограничимся графами несопоставимости (т. Е. Мы хотим подсчитать максимальные антицепи в конечном множестве)? Этот вопрос кажется достаточно...
Паритет-L, также известный как L, представляет собой набор языков, распознаваемых недетерминированной машиной Тьюринга, которые могут различать только четное число или нечетное число путей «принятия». Недавно связанный вопрос был задан Ниль де Бодрап.⊕⊕\oplus Мой вопрос заключается в следующем: Мы...
Пусть квадрат n × nN×Nn\times n вещественной матрицы AA{\bf A} и два вектора ИксИкс{\bf x} и бб{\bf b} длины NNn такие, что A x = b .AИксзнак равноб,{\bf A}{\bf x}={\bf b}. Решение для ИксИкс{\bf x} помощью стандартного исключения Гаусса дает совокупную сложность почти O ( n3)О(N3)O(n^3) . Однако...
В определении (сильной) управляемости с фиксированными параметрами временная граница является выражением вида где входной экземпляр - ( x , k ) с параметром k , p - многочлен, а f - вычислимая функция.е( к ) . р ( | х | ) ,е(К),п(|Икс|),f(k).p(|x|),( х , к )(Икс,К)(x,k)ККkппpееf Можно заменить...
У меня есть вопрос, касающийся СЕРФ-сводимости Impagliazzo, Paturi и Zane и субэкспоненциальных алгоритмов. Определение SERF-сводимости дает следующее: Если P1P1P_1 является SERF-сводимым к P2P2P_2 и существует алгоритм O(2εn)O(2εn)O(2^{\varepsilon n}) для P2P2P_2 для каждого...
Теорема Раза о параллельном предсказании является важным результатом в PCP, аппроксимации и т. Д. Теорема оформилась следующим образом. Игра , где S , T , A , B - конечные множества, π - распределение по S × T и предикат V : S × T × A × B → { 0 , 1 } . Определить значение игры v ( G ) = max...
Есть ли доказательство того, что эмуляция машины Тьюринга на забывающей машине Тьюринга не может быть выполнена менее чем за O(mlogm)O(mlogm)\mathcal{O}\left(m\log m\right) где mmm - это число шагов, которые машина Тьюринга использует? Или это только верхняя граница? Витани утверждает, что в...
Я хотел бы знать об истории этих двух терминов: « эффективный », « выполнимый ». Кто использовал их в отношении вычислений / алгоритмов в первый раз? (в современном понимании этих терминов, т.е. 20-го века). Как они стали мейнстримом? Как эти два термина начали использоваться как синонимы? Я знаю,...
Известно ли, что задача множества вершин обратной связи на неориентированных плоских графах ограниченной степени является трудной?Н
Может ли кто-нибудь перечислить некоторые известные проблемы, удовлетворяющие следующим условиям: 1. has a generalization problem that is known to be NP-complete 2. has not been proved to be NP-complete nor has a known polynomial time solution....
Существует несколько хорошо известных результатов оценки нижнего предела размера схемы основанных на случайных ограничениях и лемме о переключении .AC0AC0\mathsf{AC^0} Можем ли мы разработать результат леммы о переключении, чтобы доказать нижнюю оценку размера для цепей (аналогично нижним оценкам...
Гауссовское исключение делает определитель матрицы полиномиальным временем вычислимым. Снижение сложности в вычислении детерминанта, которое в противном случае является суммой экспоненциальных членов, обусловлено наличием альтернативных отрицательных признаков (отсутствие которых делает вычисление...
Наименьшая известная формула для детерминанта имеет размер соответствии с фольклором (или Ран Разу в своей статье « Многолинейные формулы для перманента и детерминанта имеют суперполиномиальный размер» ).NO (журналн )NО(журналN)n^{\mathcal O(\log n)} У вас есть ссылки на это? В частности, что это...
Алгоритм тестирования распределения для свойства распределения P (которое является лишь некоторым подмножеством всех распределений по [n]) разрешает доступ к выборкам в соответствии с некоторым распределением D и должен решить (whp), если или ( здесь, как правило, расстояние). Наиболее...
Мне кажется, что специалисты по машинному обучению / интеллектуальному анализу данных знакомы с P и NP, но редко говорят о некоторых более тонких классах сложности (например, NC, BPP или IP) и их последствиях для эффективного анализа данных. Есть ли какой-нибудь обзор работы, выполняющей...
Мы говорим, что функция f:N→Nf:N→Nf:\mathbb{N}\rightarrow\mathbb{N} является конструируемой во времени , если существует детерминированная многоленточная машина Тьюринга MMM которая на всех входах длины nnn делает не более f(n)f(n)f(n) шагов, и для каждого существует некоторый вход длина на которой...
Легко видеть, что если то есть общие проблемы поиска N P, которые не могут быть решены за полиномиальное время (создайте проблему общего поиска, имея как свидетелей для членства, так и свидетелей для не состоятельности).Н П∩coNP≠PNP∩coNP≠P\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}NPNп\mathsf{NP}...
Задача разбиения слабо NP-полна, поскольку имеет алгоритм полиномиального (псевдополиномиального) времени, если входные целые числа ограничены каким-либо полиномом. Однако 3-разбиение является сильно NP-полной задачей, даже если входные целые числа ограничены полиномом. Предполагая, , можем ли мы...
Напомним , что ширина резолюции опровержение RRR из формулы CNF FFF представляет максимальное число литералов в любом пункте , происходящих в RRR . Для каждого в 3-CNF wwwесть неудовлетворительные формулы FFF каждое опровержение разрешения FFF требует ширины не менее www . Мне нужен конкретный...