Сокращение - это превращение одной проблемы в другую. Примером использования сокращения может быть показ, если проблема P неразрешима. Это может быть достигнуто путем преобразования или выполнения задачи решения в неразрешимую проблему. Если это может быть достигнуто, то мы показали, что эта проблема P неразрешима. п P
Почему большинство людей предпочитают использовать сокращения «один-один» для определения NP-полноты вместо, например, сокращений
Задача суммы квадратных корней задает для заданных двух последовательностей a1,a2,…,ana1,a2,…,ana_1, a_2, \dots, a_n и b1,b2,…,bnb1,b2,…,bnb_1, b_2, \dots, b_n натуральных чисел, является ли сумма ∑iai−−√∑iai\sum_i \sqrt{a_i} меньше, равно или больше суммы . Статус сложности этой проблемы открыт;...
Предполагается, что случайность не расширяет возможности алгоритмов полиномиального времени, то есть предполагается, что будет выполняться. С другой стороны, случайность, по-видимому, оказывает совершенно иное влияние на сокращение полиномиального времени . По хорошо известным результатам Valiant и...
Теорема Валианта-Вазирани говорит, что если существует алгоритм полиномиального времени (детерминированный или рандомизированный) для разграничения между формулой SAT, которая имеет ровно одно удовлетворяющее назначение, и формулой неудовлетворительного типа, - тогда NP = RP . Эта теорема доказана...
Сегодня в блоге Скотта Ааронсона приведен список интересных открытых задач / задач по сложности. Один из них привлек мое внимание: Создайте публичную библиотеку из 3SAT-экземпляров, используя как можно меньше переменных и предложений, что может привести к значительным последствиям в случае ее...
Есть ли пример языка, который есть в , но где мы не можем доказать этот факт непосредственно, показывая, что существует полиномиальное свидетельство о членстве в этом языке?NпNPNP Вместо этого тот факт, что язык находится в может быть доказан путем сведения его к другому языку в , где связь между...
Некоторые NP-сложные задачи, которые являются экспоненциальными на общих графах, являются субэкспоненциальными на плоских графах, потому что ширина дерева не более и они экспоненциальны в ширине дерева.4.9 | В( G ) |------√4.9|V(G)|4.9 \sqrt{|V(G)|} В основном меня интересует, существуют ли...
Подсчет количества совершенных совпадений в двудольном графе сразу сводится к вычислению перманента. Поскольку поиск идеального соответствия в двудольном графе есть в NP, существует некоторое сокращение от двудольных графов к перманенту, но это может привести к неприятному полиномиальному взрыву,...
Ясно, что сокращение от CLIQUE до k-Color, потому что они оба NP-Complete. Фактически, я могу построить один, составив сокращение от CLIQUE до 3-SAT с сокращением от 3-SAT до k-Color. Мне интересно, есть ли разумное прямое сокращение между этими проблемами. Скажем, сокращение, которое я мог бы...
Некоторые из вас, возможно, следили за этим вопросом , который был закрыт из-за отсутствия уровня исследования. Итак, я извлекаю часть вопроса, которая находится на исследовательском уровне. Помимо «более простых» техник, таких как приведение к сортировке или задача, полная по EXPTIME, какие методы...
Это похоже на « Алгоритмы из Книги ». Хотя сокращения также являются алгоритмами, я подумал, что сомнительно, что можно подумать о сокращении в ответ на вопрос об алгоритмах из книги. Отсюда отдельный запрос! Сокращения всех видов приветствуются. Я начну с действительно простого сокращения от...
Этот вопрос касается связи между нормальным умножением двоичных чисел и модулем умножения полиномов. Чтобы конкретизировать вопрос, я в идеале хотел бы знать, существует ли лучшее решение вопроса из Кнута тома. 2, 3-е издание, стр. 420, чем приведенное в книге. «Может ли умножение многочленов по...
В статье Томаса Дж. Шефера « Сложность проблем с удовлетворенностью» автор упомянул, что This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the relational complexity...
В этом вопросе мы, кажется, идентифицировали естественную проблему, которая является NP-полной при рандомизированных сокращениях, но, возможно, не при детерминированных сокращениях (хотя это зависит от того, какие недоказанные предположения в теории чисел верны). Известны ли еще такие проблемы?...
USTCONN - это проблема, которая требует решения о том, существует ли путь от исходной вершины sss до целевой вершины ttt в графе GGG , где все они представлены как часть входных данных. Омер Рейнгольд показал, что USTCONN находится в L (doi: 10.1145 / 1391289.1391291 ). Доказательство создает...
Здесь цель состоит в том, чтобы свести произвольную задачу SAT к 3-SAT за полиномиальное время, используя наименьшее количество предложений и переменных. Мой вопрос мотивирован любопытством. Менее формально я хотел бы знать: «Каково« наиболее естественное »сокращение с SAT до 3-SAT?» Теперь...
Недавно я прочитал доказательство, которое намеревалось показать, что проблема была сильно NP-трудной, просто сводя ее (за полиномиальное время) от сильно NP-трудной задачи. Это не имело никакого смысла для меня. Я бы подумал, что вам нужно будет показать, что любые числа, использованные в...
Известно, что пересечение трех общих матроидов является NP-трудным ( источником ), что осуществляется посредством сокращения из гамильтонова цикла. Сокращение использует один графический матроид и два матроида связи. Частный случай проблемы, над которой я работаю, может быть решен путем пересечения...
Как всем известно, знаменитая книга Гэри и Джонсона (и многие другие) дает превосходный справочник по технике редукции в классической обстановке. Существуют ли какие-либо обзоры или книги на тему техники редукции в параметризованном алгоритме, скажем, редукция...
Я надеялся, что кто-нибудь сможет объяснить мне, почему именно проблема подмножеств является сильно NP-трудной, в то время как проблема сумм подмножеств является NP-трудной. Подмножество Сумма: Дано и Т , существует ли подмножество X ' такое , что Σ я ∈ Х ' х я = Т .Икс= { х1, . , , ,...