NP-Complete задачи, которые допускают эффективный алгоритм под обещанием уникального решения

14

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

Благодаря экономному сокращению (сокращению, которое сохраняет количество решений) легко увидеть, что большинство NP-полных задач (я мог бы подумать) также не допускают эффективного алгоритма даже при условии, что существует не более одного решения. (если только ). Примерами могут быть VERTEX-COVER, 3-SAT, MAX-CUT, 3D-MATCHING.NP=RP

Поэтому мне было интересно, существует ли какая-либо NP-полная проблема, которая, как известно, допускает алгоритм с множественным временем в соответствии с обещанием уникальности.

дьявол
источник
12
Это не очень хороший ответ, но есть много NP-полных задач, экземпляры которых всегда имеют либо ноль, либо несколько решений. Рассмотрим граф 3-раскраски, например; решения приходят группами по 6, так как вы всегда можете изменить цвета. Любая такая проблема имеет алгоритм полиномиального времени, обещая не более одного решения. В частности, если существует не более 3-х раскрасок, их не может быть, поэтому алгоритм может просто отклонить.
Михаил Рудой
4
Задача о гамильтоновом цикле допускает более быстрый (но все же экспоненциальный) алгоритм времени по обещанию уникальности. Он не дает прямого ответа на ваш вопрос, потому что он не полиномиален, но, по крайней мере, это проблема с другим поведением, чем SAT
ivmihajlin
4
Как и в комментарии Михаила Рудого, проверка существования гамильтонова цикла в 3-регулярных графах тривиальна с предположением единственности. Каждое ребро участвует в четном числе гамильтоновых циклов, поэтому никогда не может быть ровно одного.
Дэвид Эппштейн

Ответы:

10

Не известно ни одной NP-полной задачи, допускающей использование алгоритма за полиномиальное время с обещанием уникальности. Теорема Валианта и Вазирани применима к любой известной естественной NP-полной задаче.

NP

Мухаммед Аль-Туркистани
источник
2
См. Также теорему 2.1: wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf
Мухаммед Аль-Туркистани,