Существуют ли какие-либо NP-полные задачи, для которых известен алгоритм, согласно которому ожидаемое время выполнения является полиномиальным (для некоторого разумного распределения по экземплярам)? Если нет, то существуют ли проблемы, для которых было установлено существование такого алгоритма?...
Редактировать: я сначала неправильно сформулировал свое ограничение (2), теперь оно исправлено. Я также добавил больше информации и примеров. С некоторыми коллегами, изучающими какой-то другой алгоритмический вопрос, мы смогли свести нашу проблему к следующей интересной проблеме, но мы не смогли...
Ясно, что любая проблема, которая разрешима в детерминированном пространстве журналов ( ), выполняется в самое большее полиномиальное время ( ). Существует множество классов сложности между и . Примеры включают , , , , , . Широко распространено мнение , что .P L P N L L o g C F L N C i S A C i A C...
РЕДАКТИРОВАТЬ (v2): в конце добавлен раздел о том, что я знаю о проблеме. РЕДАКТИРОВАТЬ (v3): Добавлено обсуждение пороговой степени в конце. Вопрос Этот вопрос в основном справочный запрос. Я не знаю много о проблеме. Я хочу знать, была ли предыдущая работа по этой проблеме, и если да, может ли...
Существует богатая литература и, по крайней мере, одна очень хорошая книга, в которой излагаются известные значения твердости аппроксимации для NP-трудных задач в контексте мультипликативной ошибки (например, 2-аппроксимация для покрытия вершин оптимальна при условии UGC). Это также включает хорошо...
Гипотеза Субхаша Хота об уникальных играх - одно из активных направлений в теории сложности. Какие доказательства у нас есть для этого? Какие доказательства у нас есть против этого?...
В настоящее время биткойн имеет систему проверки работоспособности (PoW) с использованием SHA256. Другие хеш-функции используют графы доказательства работы системы, частичное обращение хеш-функций. Можно ли использовать проблему принятия решений в теории узлов, такую как распознавание узлов, и...
Доступ к оракулу обеспечит значительное, сверхполиномиальное ускорение для всего в (при условии, что набор не пуст). Тем не менее, не совсем ясно, сколько выиграет от этого доступа к оракулу. Конечно, ускорение в не может быть суперполиномиальным, но оно может быть полиномиальным. Например, можем...
Известно, что гамильтонов цикл (для краткости Хэм) NP-полон, а планарный цикл Хэма NP-полон. Доказательство для плоского цикла Хэма не из цикла Хэма. Есть ли хороший гаджет, который с учетом графа G заменит все пересечения некоторым плоским гаджетом, чтобы у вас был планарный граф G 'такой, что G...
Этот вопрос связан с ответом, который я разместил в ответ на другой вопрос. Задача с 3 разделами представляет собой следующую проблему: Экземпляр : положительные целые числа a 1 ,…, a n , где n = 3m, а сумма n целых чисел равна mB, так что каждый a i удовлетворяет B / 4 <a i <B / 2. Вопрос :...
Каковы убедительные причины верить L ≠ PL≠PL\neq P ? L - класс алгоритмов лог-пространства с указателями на вход. Предположим, что L = P на данный момент. Как будет выглядеть алгоритм лог-пространства для P-полной задачи в общих...
Ясно, что сокращение от CLIQUE до k-Color, потому что они оба NP-Complete. Фактически, я могу построить один, составив сокращение от CLIQUE до 3-SAT с сокращением от 3-SAT до k-Color. Мне интересно, есть ли разумное прямое сокращение между этими проблемами. Скажем, сокращение, которое я мог бы...
Недавно я видел несколько статей об arxiv, которые ссылаются на систему доказательств под названием сумма квадратов. Может кто-нибудь объяснить, что такое доказательство суммы квадратов и почему такие доказательства важны / интересны? Как они связаны с другими алгебраическими системами...
Теория сложности, с помощью таких понятий, как NP-полнота, различает вычислительные задачи, которые имеют относительно эффективные решения, и те, которые трудноразрешимы. «Мелкозернистая» сложность призвана уточнить это качественное различие в количественном руководстве относительно точного...
Что известно о сложности поиска минимальных схем, которые вычисляют SAT до длины ? nnn Более формально: какова сложность функции, которая, учитывая качестве входных данных, выводит минимальную схему C такую, что для любой формулы φ с | φ | ≤ n , C ( φ ) = S A T ( φ )...
По мотивам комментария Фортнау к моему сообщению, доказательством того, что проблема изоморфизма графов не является NпNпNP -полным , и тем фактом, что G IгяGI является главным кандидатом в NпNпNP -проблеменную проблему (не NпNпNP -полное ни в ппP ), я заинтересованы в известных доказательств , что...
В опросе Д. Бера, Ф. Грина и С. Гомера «Квантовые схемы малой глубины» (стр. 36 ACM SIGACT News, июнь 2007 г., том 38, № 2) я прочитал следующее предложение: Классическая версия (в которой вентили и имеют самое большее постоянное разветвление), очевидно, слабее, чем...
Некоторые из вас, возможно, следили за этим вопросом , который был закрыт из-за отсутствия уровня исследования. Итак, я извлекаю часть вопроса, которая находится на исследовательском уровне. Помимо «более простых» техник, таких как приведение к сортировке или задача, полная по EXPTIME, какие методы...
Я знаю, что тривиально функция OR для переменных может быть точно представлена полиномом следующим образом: , который имеет степень .х 1 , ... , х п р ( х 1 , ... , х п ) р ( х 1 , ... , х п ) = 1 - П п я = 1 ( 1 - х я ) пNnnИкс1, … , ХNx1,…,xnx_1,\ldots, x_nр ( х1, … ,...
Рассмотрим задачи оптимизации следующего вида. Пусть f(x)f(x)f(x) - вычислимая функция полиномиального времени, которая отображает строку xxx в рациональное число. Задача оптимизации заключается в следующем: что максимальное значение f(x)f(x)f(x) над nnn -битовый строки xxx ?...