Класс сложности состоит из тех -проблем, которые могут быть решены недетерминированной машиной Тьюринга за полиномиальное время, которая имеет не более одного приемлемого вычислительного пути. То есть решение, если оно есть, является уникальным в этом смысле. Весьма маловероятно, что все -проблемы...
Теорема Валианта-Вазирани говорит, что если существует алгоритм полиномиального времени (детерминированный или рандомизированный) для разграничения между формулой SAT, которая имеет ровно одно удовлетворяющее назначение, и формулой неудовлетворительного типа, - тогда NP = RP . Эта теорема доказана...
Рассмотрим следующую проблему: учитывая формулу CNF и присвоение, которое удовлетворяет этой формуле, есть ли другое удовлетворяющее назначение для этой формулы? В чем сложность этой проблемы? (Это наверняка есть в NP, но это также NP-hard?) Что если вам не дано назначение, и вы просто хотите...
РЕДАКТИРОВАТЬ в 2011/02/08: После того, как некоторые ссылки были найдены и прочитаны, я решил разделить оригинальный вопрос на два отдельных. Вот часть, касающаяся UP vs NP, для части синтаксических и семантических классов см. Преимущества для синтаксических и семантических классов ....
Я пытаюсь выяснить, есть ли какие-либо общие результаты или примеры, касающиеся NP-полноты проблемы поиска второго решения NP-полной задачи. Точнее, меня интересуют любые проблемы следующего вида: Учитывая решение для экземпляра NP-полной задачи, есть ли решение для ?SSSяяIS'≠ SS'≠SS' \neq SяяI...
Следуя предложению Джоша Грохова, я превращаю свой комментарий из предыдущего вопроса в новый. Какие доказательства у нас есть для ?UP≠NPUP≠NP\mathsf{UP} \neq \mathsf{NP} Здесь - это класс языков, распознаваемых недетерминированными машинами Тьюринга за полиномиальное время, которые имеют...
Преамбула. Класс сложности AM - это те проблемы, которые могут быть решены с помощью двухсторонней интерактивной системы доказательств между прувером «Мерлин» и верификатором «Артур». Проблема, которая проверяет некоторое свойство объекта X, заключается в AM, если: Для случаев ДА для случайного...
Недавно я читал очень хорошую статью от Valiant и Vazirani, в которой показано, что если , то не может быть эффективного алгоритма для решения SAT, даже при условии, что он либо неудовлетворителен, либо имеет уникальное решение. , Таким образом, показывая, что SAT не допускает эффективного...
«Вторая » проблема - это проблема принятия решения о существовании другого решения, отличного от некоторого данного решения для экземпляра проблемы.XXX Для некоторых задач с завершением второй версией решения является -complete (решающий вопрос о существовании другого решения для задачи с частичным...