Probleme, die unter randomisierten oder P / Poly-Reduktionen NP-vollständig sind.

In dieser Frage scheinen wir ein natürliches Problem identifiziert zu haben, das unter randomisierten Reduktionen NP-vollständig ist, möglicherweise jedoch nicht unter deterministischen Reduktionen (obwohl dies davon abhängt, welche unbewiesenen Annahmen in der Zahlentheorie zutreffen). Sind noch andere Probleme bekannt? Gibt es irgendwelche natürlichen Probleme, die unter P / Poly-Reduktionen NP-vollständig sind, von denen jedoch nicht bekannt ist, dass sie unter P-Reduktionen liegen?

cc.complexity-theory np-hardness big-list randomness reductions Peter Shor
quelle

Unique SAT ist -hart unter randomisierter Reduktion.

N P

$NP$

Mohammad Al-Turkistany

Ich verstehe nicht, warum Unique SAT nicht als Antwort gelten sollte (obwohl das nicht ganz das war, wonach ich gesucht habe). Ich denke, das ist ein natürliches Problem.

Peter Shor

Ich wollte nur hinzufügen, dass das kürzeste Vektorproblem für LLL unter der Norm für randomisierte Reduktionen ( von Ajtai hier ) NP-schwer ist. Soweit ich weiß, ist es nicht bekannt, dass es unter nicht zufälligen Reduktionen NP-hart ist, daher entspricht es nicht Ihren Kriterien, aber ich dachte, es sollte trotzdem erwähnt werden.

L_{2}

$L_2$

user834

@Joshua: In einigen NP-vollständigen Problemen im Zusammenhang mit Rätseln (wie Sudoku) ist die Eindeutigkeit einer Lösung eine natürliche Annahme. Ich vermute, dass dies das SAT mit höchstens einer Lösung (ich ziehe es vor, es als eindeutiges SAT zu bezeichnen) natürlicher macht, als es zunächst scheinen mag.

Tsuyoshi Ito

Warum schreibt jeder Antworten in Kommentare? : P

Hsien-Chih Chang 張顯之

Antworten:

Unter Randomized Reduction with Probability (auch als -Reduzibility bekannt) finden Sie unter " Über Unique Satisfiability und Randomized Reductions " Probleme $\frac{1}{2}$ $\gamma$

Lineare Teilbarkeit
Binäre quadratische Diophantingleichungen

sind NP-vollständig, aber das Gleiche ist nicht bekannt für deterministische Reduktionen (soweit ich weiß, für eine etwas veraltete Diskussion dieser Situation siehe hier ). -Reduzierbarkeit wurde von Leonard Adleman und Kenneth Manders in der Arbeit " Reducibility, Randomness and Intractibility " vorgestellt (Beweise für die oben genannten Probleme wurden auch dort vorgeschlagen). $\gamma$

Es gibt andere Beispiele in " Ein Katalog von Komplexitätsklassen ", aber ich habe nicht überprüft, was über ihre NP-Vollständigkeit unter deterministischen Reduktionen bekannt ist.

Oleksandr Bondarenko
quelle

Wie von Peter vorgeschlagen, habe ich meinen Kommentar in eine Antwort umgewandelt.

Der Valiant-Vazirani-Satz besagt, dass, wenn Unique SAT ist, . Um ihren Satz zu beweisen, haben sie gezeigt, dass das Versprechungsproblem Unique SAT unter randomisierten Reduktionen -hart ist. $\in P$ $NP=RP$ $NP$

[1] Valiant, Leslie; Vazirani, Vijay. "NP ist so einfach wie das Auffinden einzigartiger Lösungen", Theoretical Computer Science, 47: 85–93

Mohammad Al-Turkistany
quelle

Wie von Peter vorgeschlagen, habe ich meinen Kommentar in eine Antwort umgewandelt:

$L_2$ $NP$

user834
quelle