Langsamste Eins-zu-Eins-Reduktion?

13

Wenn wir beweisen wollen , dass ein ist -komplette, dann wird der Standard - Ansatz ist ein Polynom berechenbare viel eine Reduktion eines bekannten zu zeigen -komplette Problem zu . In diesem Zusammenhang brauchen wir keine feste Grenze für die Laufzeit der Reduktion. Es genügt, jedes Polynom gebunden zu haben , so dass es möglicherweise einen sehr hohen Grad hat.LNPNPNPL

Für natürliche Probleme ist die Schranke jedoch typischerweise ein Polynom niedrigen Grades (definieren wir low als etwas in den einzelnen Ziffern). Ich behaupte nicht, dass dies immer der Fall sein muss, aber mir ist kein Gegenbeispiel bekannt.

Frage: Gibt es ein Gegenbeispiel? Dies wäre eine vielfach berechenbare Vielfachreduktion zwischen zwei natürlichen vollständigen Problemen, so dass für denselben Fall keine schnellere Reduktion bekannt ist und die bekannteste gebundene Polynomlaufzeit ein Polynom hohen Grades ist.NP

Hinweis: Für natürliche Probleme in werden gelegentlich große oder sogar große Exponenten benötigt , siehe Algorithmen zur Polynomzeit mit großem Exponenten / großer Konstante . Ich frage mich, ob dies auch bei Reduktionen bei natürlichen Problemen der Fall ist.P

Andras Farago
quelle
2
Dieses Papier ist möglicherweise relevant. Die NP-Vollständigkeit bei sehr begrenzten Reduktionen (z. B. AC0 oder logspace) ist interessant, da die meisten Reduktionen intuitiv "gadgetbasiert" sind, was darauf zurückzuführen ist, dass die Berechnung ein lokales Phänomen ist
Joe Bebel,
3
Wir beschäftigen uns normalerweise mit Reduktionen, die eine Instanz von SAT (oder ein einfaches NPC-Problem) in eine Instanz von umwandeln . Aber das Denken in der umgekehrten Art und Weise L p S A T führt zu Polynomialzeitreduktion mit embarassing Exponenten (dh in der realen Welt-Versuch ein Problem mit einem SAT - Solver zu lösen) :-). Eine ganz natürliche Klasse von Problemen, mit denen ich vertraut bin, ergibt sich aus vollständigen PSPACE-Spielen, wenn Sie einige Einschränkungen hinzufügen (Zeit, Anzahl der Züge, begrenzte Besuche an Orten, ...), die dazu führen, dass sie in NP fallen, und Versuchen Sie dann, sie mit einem SAT-Solver zu lösen, dh eine effiziente Reduktion auf SAT zu finden. LLpSAT
Marzio De Biasi
Ich erinnere mich, dass wir eine verwandte Frage zu natürlichen NP-Problemen hatten, für die große Zertifikate erforderlich sind (z. B. untere Schranken für die Komplexität von Beweisen), aber ich konnte sie nicht finden.
Kaveh
1
@Kaveh: Einer gehört mir: " Natürliche NP-vollständige Probleme mit" großen "Zeugen " :-)
Marzio De Biasi
3
Nach den Hierarchiesätzen gibt es in NP Probleme mit nichtdeterministischen Zeituntergrenzen, die Polynome beliebig großen Grades sind. Pick einige Probleme , dass mindestens erfordert nicht deterministisch Schritte, für d 20 . Angenommen, es gibt eine 1: 1-Reduktion von diesem Problem auf SAT, die höchstens n c Mal verwendet. Dann kann die SAT-Instanz nicht größer als n c Bits sein. Dies kann dann mit höchstens n 2 c nicht deterministischen Schritten entschieden werden. Daher ist c d / 2 10ndd20ncncn2ccd/210. Wenn Sie möchten, dass das Problem natürlich ist, fragen Sie im Wesentlichen nach natürlichen Problemen, die nicht in NTIME ( ) auftreten. nd
András Salamon

Antworten:

3

Allender schlägt vor, die Antwort ist nein:

Es scheint kein Paar natürlicher NP-vollständiger Probleme A und B bekannt zu sein, bei denen eine Reduktion von A nach B bekanntermaßen mehr als lineare Zeit erfordert (selbst unter der Annahme, dass P NP ist).

Referenz:

E. Allender und M. Koucký, Untere Schranken durch Selbstreduzierbarkeit verstärken . Journal of the ACM 57, 3, Artikel 14 (März 2010).

Mohammad Al-Turkistany
quelle
Könnten Sie bitte einen Link zu dem Artikel, in dem Allender dies schreibt, oder eine Referenz angeben?
Andras Farago
1
@AndrasFarago Der Link wird bereitgestellt. Klicken Sie auf Allender :).
Mohammad Al-Turkistany
Entschuldigung, ich habe den Link verpasst. Nach Durchsicht der Zeitung fand ich eine weitere interessante Aussage: "Es ist kein natürliches NP-vollständiges Problem außerhalb von NTIME (n) bekannt." (Es steht im Satz unmittelbar vor dem zitierten Teil.)
Andras Farago
5
Ich schlage vor, bei der Interpretation dieser Aussagen ein gewisses Maß an Diskretion zu wahren. In einigen Fällen ist beispielsweise nur eine quadratische Reduktion bekannt. Beispielsweise kann eine Reduktion auf eine planare Version eines NP-vollständigen Problems eine quadratische Anzahl von Überkreuzungsgeräten verwenden. Untergrenzen sind knifflig und viele Dinge sind "nicht bekannt, dass sie erforderlich sind".
Joe Bebel
1
@JoeBebel Ich stimme zu, dass bei der Interpretation dieser Aussagen Diskretion erforderlich ist. Beispielsweise hatten die Autoren in der Aussage, dass "kein natürliches NP-vollständiges Problem außerhalb von NTIME (n) bekannt ist", wahrscheinlich eine engere Interpretation von "natürlich" im Sinn. Vielleicht meinen sie etwas in der Art: Ein natürliches Problem ist eines, das die Menschen aufgrund praktischer Motivation wirklich lösen möchten.
Andras Farago