Вопросы с тегом «cc.complexity-theory»

18
Легко ли изоморфизм индуцированного подграфа на бесконечном подклассе?

Существует ли последовательность неориентированных графов , где каждый имеет ровно вершин, и проблема{ CN}n ∈ N{СN}N∈N\{C_n\}_{n\in \mathbb N}СNСNC_nNNn При заданном и графе является ли индуцированным подграфом в ?NNnграммграммGСNСNC_nграммграммG известно, что он находится в классе ? (Например,...

18
Естественный кандидат против гипотезы об изоморфизме?

Знаменитая гипотеза об изоморфизме Бермана и Хартманиса говорит, что все -полные языки полиномиально по времени изоморфны (p-изоморфны) друг другу. Ключевое значение гипотезы является то , что она предполагает P ≠ N P . Она была опубликована в 1977 году, и часть подтверждающих доказательств, что...

18
Проблемы с эффективным решением за исключением небольшой доли ресурсов

Проблема остановки для машин Тьюринга, возможно, является каноническим неразрешимым множеством. Тем не менее, мы доказываем, что существует алгоритм, решающий почти все его экземпляры. Таким образом, проблема остановки является одной из растущих коллекций тех, кто демонстрирует феномен «черной...

18
Сложность восстановления матрицы смежности из ее квадрата

Меня интересует следующая проблема: Имеется ли матрица, существует ли неориентированный граф на вершинах, квадрат матрицы смежности которых является этой матрицей?n×nn×nn\times nnnn Известна ли вычислительная сложность этой проблемы? Примечания: Конечно, это также можно сформулировать как задачу...

18
Доказательство того, что верхние границы схемы для

В официальном описании проблемы Клея для P против NP он заявил , что будет следовать из показывая , что «каждый язык в Е [класс языков , распознаваемый в экспоненциальное время с детерминированной машиной Тьюринга] может быть вычислено с помощью булева семейства схем < в п > такое , что , по...

18
Хаос и

Я заинтересован в изучении связей между «хаосом» или, в более широком смысле, динамическими системами и вопросом . Вот пример типа литературы, которую я ищу:п= Nппзнак равноNпP{=}NP Эрчи-Раваш, Мария и Золтан Торошкай. «Твердость оптимизации как переходный хаос в аналоговом подходе к удовлетворению...

18
Есть ли какие-нибудь неполные эвристические проблемы с NP?

Существуют ли какие-либо NP-полные проблемы с бесконечным подмножеством экземпляров такие, что принадлежность к может быть решена за полиномиальное время, и для всех , может быть решена за полиномиальное время? (Предполагая )ΦΦ\Phix ∈ Φ x P ≠ N PΦΦ\Phix ∈ Φx∈Φx \in \PhiИксxxп≠ NпP≠NPP \neq...

17
H-свободная проблема сокращения

Предположим, вам дан связный простой неориентированный граф H. Проблема H-свободного среза определяется следующим образом: Для простого неориентированного графа G существует ли разрез (разбиение вершин на два непустых множества L, R) такой, что графы, индуцированные множествами разрезов (L и R), не...

17
Альтернативное понятие сложности, основанное на разрыве между грубой силой и лучшим алгоритмом?

Как правило, эффективные алгоритмы имеют полиномиальное время выполнения и экспоненциально большое пространство решений. Это означает, что проблема должна быть простой в двух смыслах: во-первых, проблема может быть решена за полиномиальное число шагов, и, во-вторых, пространство решений должно быть...

17
МИП с эффективными пруверами

Хорошо известно, что набор языков, имеющих интерактивные системы доказательства с двумя доказательствами, в которых верификатор работает за полиномиальное время (MIP), является NEXP. Но известны ли пределы силы таких интерактивных доказательств, когда доказатели ограничены в силе? Например, что...

17
Является ли

В «последнем абзаце» «первой страницы» следующего документа: Викраман Арвинд , Йоханнес Коблер , Уве Шенинг , Райнер Шулер , "Если у NP есть схемы полиномиального размера, то MA = AM", Теоретическая информатика, 1995. Я столкнулся с несколько нелогичным утверждением:...

17
Руководство для начинающих по дерандомизации

Я нашел книгу « Попарная независимость и дерандомизация» по этому вопросу, но она больше ориентирована на исследования, чем на учебники. Я новичок в теме «Дерандомизация», и поэтому я хотел знать, с какой ссылки начать? Я предпочитаю тот, который обсуждает литературу и историю, а также технические...

17
Твердость параметризованной CLIQUE?

Пусть 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 содержит пропорцию от всех возможных ребер....

17
Дурачить произвольные симметричные функции

Распределение называется ϵ- обмануть функцию f, если | E x ∈ U ( f ( x ) ) - E x ∈ D ( f ( x ) ) | ≤ ϵ . И говорят, что он обманывает класс функций, если он обманывает каждую функцию в этом классе. Известно , что & epsi -biased пространство дурака класс паритетов над подмножествами. (см....

17
Структура патологических случаев для симплексных алгоритмов

Насколько я понимаю, все известные детерминированные сводные правила для симплексных алгоритмов имеют конкретные входные данные, для которых алгоритму требуется экспоненциальное время (или, по крайней мере, не полиномиальное), чтобы найти оптимальный. Давайте назовем эти случаи «патологическими»,...

17
Эффективные алгоритмы логарифмического пространства

Легко видеть, что любая проблема, которая разрешима в детерминированном пространстве журналов ( ), выполняется в самое большее полиномиальное время ( ). Многие известные алгоритмы логарифмического пространства (например, ненаправленная st-связность, изоморфизм плоских графов) работают в где безумно...

17
Сложность поиска второго решения при правильном решении NP-полной задачи

Я пытаюсь выяснить, есть ли какие-либо общие результаты или примеры, касающиеся NP-полноты проблемы поиска второго решения NP-полной задачи. Точнее, меня интересуют любые проблемы следующего вида: Учитывая решение для экземпляра NP-полной задачи, есть ли решение для ?SSSяяIS'≠ SS'≠SS' \neq SяяI...

17
Теория категорий, вычислительная сложность и комбинаторика связей?

Я пытался прочитать « Жемчужины разработки функциональных алгоритмов », а затем « Алгебру программирования », и есть очевидное соответствие между рекурсивно (и полиномиально) определенными типами данных и комбинаторными объектами, имеющими то же самое рекурсивное определение и впоследствии ведущим...

17
PARITY в QAC_0 (если это имеет смысл)

Как хорошо известно, PARITY не может быть выполнено в многоразмерных схемах с постоянной глубиной, и на самом деле схемы с постоянным углублением требуют количества входов EXP. А как насчет схем QUANTUM? а) Можно ли выполнить PARITY с помощью квантового контура, который имеет постоянную глубину и...