Пусть 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 содержит пропорцию от всех возможных ребер....
Укороченная версия. Первоначальное доказательство того, что # 2-SAT является #P -завершенным, фактически показывает, что экземпляры # 2-SAT являются монотонными (без учета отрицаний каких-либо переменных) и двудольными (график, образованный предложениями над Переменный является двудольным графом)...
Читая статью об использовании алгебраических методов для обнаружения некоторых индуцированных подграфов, кажется, что реберный идеал является важным инструментом, соединяющим коммутативную алгебру и теорию графов. Поскольку я не знаком с вычислениями алгебраических объектов, есть ли хорошие ссылки...
Многие теоремы и «парадоксы» - диагонализация Кантора, неразрешимость хетлинга, неразрешимость колмогоровской сложности, неполнота Гёделя, неполнота Хаитина, парадокс Рассела и т. Д. - все имеют по существу одно и то же доказательство диагонализацией (обратите внимание, что это более конкретно, чем...
Сложность схемы с ограниченной глубиной является одной из основных областей исследования в теории сложности схемы. Эта тема имеет происхождение в результатах типа «функция четности не в » и « функция mod не вычисляется », где - класс языков, разрешимых по неоднородности, постоянной глубине,...
Нижняя граница Блума 3n−o(n)3N-о(N)3n-o(n) - это лучшая известная нижняя граница схемы по полному базису для явной функции f:{0,1}n→{0,1}f:{0,1}n→{0,1}f : \{0,1\}^n \to \{0,1\} , ср. Юкна ответ на этот вопрос для связанных результатов. Каковы наиболее известные нижние оценки, если диапазон fff...
Недетерминированная логическая схема имеет, помимо обычных входов , набор «недетерминированных» входов . Недетерминированная схема принимает вход если существует такой, что выход схемы включен . Аналогично (класс языков, разрешимых схемами полиномиального размера), можно определить как класс...
Я ищу естественные примеры эффективных алгоритмов (т.е. в полиномиальном времени) их правильность и эффективность могут быть доказаны конструктивно (например, в PRAпрAPRA или ), ноHAЧАСAHA не известно никаких доказательств, использующих только эффективные концепции (то есть мы не знаем, как...
Фон Известно , что существует оракул такое , что .P S P A C E A ≠ P H AAAAPSPACEA≠PHAPSPACEA≠PHAPSPACE^A \neq PH^A Даже известно, что разделение справедливо относительно случайного оракула. Неофициально можно интерпретировать это как означающее, что существует много оракулов, для которых и...
Известно, что минимальный размер цепей, функцию четности, в точности равен . Нижняя оценка доказательства основана на методе исключения ворот.U2U2U_23 ( n - 1 )3(N-1)3(n-1) Недавно я заметил, что метод исключения затвора хорошо работает и для недетерминированных цепей, и мы можем доказать нижнюю...
Как хорошо известно, PARITY не может быть выполнено в многоразмерных схемах с постоянной глубиной, и на самом деле схемы с постоянным углублением требуют количества входов EXP. А как насчет схем QUANTUM? а) Можно ли выполнить PARITY с помощью квантового контура, который имеет постоянную глубину и...
Что если что-либо известно о параметризованной сложности вычисления числа пересечений графа (наименьшее число кликов, необходимых для охвата всех его ребер)? Давно известно, что он является NP-полным, и это, очевидно, FPT, потому что у него есть ядро: если вы можете покрыть граф кликами, то...
Мне сказали, что есть несколько хороших алгоритмов полиномиального времени для аппроксимации числа простых путей в ориентированном графе от заданной начальной вершины до заданной конечной вершины t . Кто-нибудь знает хорошую ссылку на эту тему?sssTTt Справочная информация: подсчет точного числа...
Метод отрицательного противника ( ) - это SDP, характеризующий сложность квантового запроса. Это обобщение широко используемого метода противника ( A D V ), и оно преодолевает два барьера, мешающих противнику:A D V±ADВ±ADV^\pmA D VADВADV Барьер тестирования свойств: если все 0-экземпляры находятся...
задира Поскольку проблема длинная, здесь есть особый случай, который отражает ее суть. Проблема: Пусть A - детриминистический алгоритм для 3-SAT. Является ли проблема полного моделирования алгоритма A (на каждом экземпляре задачи). P-Space сложно? (Точнее, есть ли основания полагать, что эта задача...
Знаменитая картина мира Нила Иммермана выглядит следующим образом (нажмите, чтобы увеличить): Его «действительно выполнимый» класс не включает другого класса; мой вопрос тогда: Что такое проблема AC 0, которая считается непрактичной и почему?...
Не известно , если изоморфизм графов (GI) для сильно регулярных графов (SRGS) в P . Есть ли намеки на то, что это может или не может быть GI- Complete? Есть ли сильные последствия в таких случаях? (Аналогично убеждению, что GI не может быть...
Край крышки представляет собой подмножество ребер графа, что каждая вершина графа смежна по крайней мере , одного края крышки. В следующих двух статьях говорится, что подсчет краевых покрытий является # P- полным: Простая FPTAS для подсчета краевых покрытий и генерации краевых покрытий для графов...
Какое минимальное количество двоичных вентилей необходимо для вычисления И и ИЛИ из входных битов одновременно? Тривиальная верхняя граница . Я считаю, что это оптимально, но как это доказать? Стандартный метод устранения строба здесь не работает, так как, присваивая константу любой из входных...
Анализ наихудших и средних случаев - это общеизвестные меры сложности алгоритма. Недавно сглаженный анализ стал еще одной парадигмой, объясняющей, почему некоторые алгоритмы, экспоненциальные в наихудшем случае, так хорошо работают на практике, например, симплексный алгоритм. Мой вопрос - есть ли...