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

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

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

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

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

$NP$