Können wir eine Karp-Reduktion aus einer Cook-Reduktion zwischen NP-Problemen konstruieren?

10

Wir hatten mehrere Fragen zum Verhältnis von Cook- und Karp-Reduktionen . Es ist klar, dass Cook-Reduktionen (Poluring-Zeit-Turing-Reduktionen) nicht den gleichen Begriff der NP-Vollständigkeit definieren wie Karp-Reduktionen (Polynom-Zeit-Viel-Eins-Reduktionen), die normalerweise verwendet werden. Insbesondere können Cook-Reduktionen NP nicht von Co-NP trennen, selbst wenn P NP. Daher sollten wir Cook-Reduktionen nicht in typischen Reduktionsnachweisen verwenden.

Jetzt fanden die Schüler eine von Experten begutachtete Arbeit [1], die eine Cook-Reduktion verwendet, um zu zeigen, dass ein Problem NP-schwer ist. Ich habe ihnen nicht die volle Punktzahl für die Reduzierung gegeben, die sie von dort genommen haben, aber ich frage mich.

Da Cook-Reduktionen einen ähnlichen Begriff von Härte definieren wie Karp-Reduktionen, denke ich, dass sie in der Lage sein sollten, P von NPC bzw. NPC zu trennen. Co-NPC unter der Annahme von P NP. Insbesondere sollte (so etwas wie) Folgendes zutreffen:

L1NP,L2NPCKarp,L2CookL1L1NPCKarp .

Das wichtige Nugget ist, dass , wie oben erwähnt, umgangen wird. Wir "wissen" jetzt - per Definition des NPC -, dass .L 2 K a r p L 1L1NPL2KarpL1

Wie Vor bemerkt hat , ist es nicht so einfach (Notation angepasst):

Angenommen, , dann per Definition für alle Sprachen wir habe ; und wenn die obige Implikation wahr ist, dann ist und damit was noch eine offene Frage ist. L 2N P C K a r pN P L 2 C o o k L 1 L 1N P C K a R p N P C K a r p = N P C C o o kL1NPCCookL2NPCKarpNPL2CookL1L1NPCKarpNPCKarp=NPCCook

Es kann andere Unterschiede zwischen den beiden NPCs geben, aber Co-NP.

Andernfalls gibt es bekannte (nicht triviale) Kriterien für eine Kochreduktion, die eine Karp-NP-Härte impliziert, dh kennen wir Prädikate mitP

L2NPCKarp,L2CookL1,P(L1,L2)L1NPCKarp ?


  1. Zur Komplexität der Mehrfachsequenzausrichtung von L. Wang und T. Jiang (1994)
Raphael
quelle
Lassen Sie uns diese Diskussion im Chat fortsetzen
Raphael
Ist Ihre Frage, ob ? NPCKarp=NPCCookNP
Albert Hendriks
@ AlbertHendriks Ähnlich, aber nicht gleich. Ich frage nach einem Prädikat das Ihre Variante auf " " setzen würde (vgl. Erster Teil der Frage), dh wenn es Ergebnisse gibt, bei denen stärker als die NP-Mitgliedschaft ist. L 1N P P.PL1NPP
Raphael

Antworten:

4

Es ist ein allgemein offenes TCS-Problem, das Gegenstand laufender Untersuchungen ist, ob und unter welchen Bedingungen die Cook- und Karp-Reduktionen gleichwertig sind, und anscheinend eng mit der offenen NP =? coNP-Frage und anderen Komplexitätsklassen-Trennungen zusammenhängt, z. B. E =? NE (für spärliche Sprachen).

Hier sind zwei Forschungsarbeiten zu diesem Thema und weitere Hinweise auf tcs.se über eine ähnliche Frage:

vzn
quelle
Ich suche nicht nach der genauen Beziehung.
Raphael
1

Um ein Cook-vollständiges Problem mechanisch in ein Karp-vollständiges Problem umzuwandeln, muss die Sprache selbst im Allgemeinen etwas Besonderes sein .

L

L

xx=f(x)L(x)L(x)

g(x)f(g(x))

Wie Sie sehen können, werden diese Eigenschaften normalerweise nicht in der Komplexitätstheorie oder der Berechenbarkeitstheorie gesehen. Zusammenfassend ist es äußerst unwahrscheinlich, dass Cook in Karp verwandelt werden kann.

Thinh D. Nguyen
quelle