Gibt es ein natürliches Problem bei den Naturtieren, das NP-vollständig ist?

30

Jede natürliche Zahl kann als Bitsequenz betrachtet werden. Die Eingabe einer natürlichen Zahl ist also die gleiche wie die Eingabe einer 0-1-Sequenz. Daher gibt es offensichtlich NP-vollständige Probleme mit natürlichen Eingaben. Aber gibt es irgendwelche natürlichen Probleme, dh solche, die keine Kodierung und spezielle Interpretation der Ziffern verwenden? Zum Beispiel "Ist na prime?" ist so ein natürliches Problem, aber dieses ist in P. Oder "Wer gewinnt das Nim-Spiel mit Haufen der Größe 3, 5, n, n?" ist ein weiteres Problem, das ich für natürlich halte, aber wir wissen auch, dass dies bei P der Fall ist. Ich interessiere mich auch für andere Komplexitätsklassen anstelle von NP.

Update: Wie von Emil Jeřábek ausgeführt, ist NP-vollständig , wenn zu bestimmen, ob eine Lösung über die Naturals hat. Dies ist genau das, was ich als natürlich angesehen habe, mit der Ausnahme, dass hier die Eingabe drei statt nur einer Zahl ist.a,b,cN,ax2+byc=0

Update 2: Und nach mehr als vier Jahren Wartezeit hat Dan Brumleve eine "bessere" Lösung vorgeschlagen - beachten Sie, dass diese aufgrund der zufälligen Reduzierung immer noch nicht vollständig ist.

domotorp
quelle
1
Ich kenne ein NEXP-vollständiges Kachelproblem, bei dem die Eingabe eine Ganzzahl n ist und das Problem darin besteht, zu bestimmen, ob es eine gültige Kachelung eines nxn-Gitters gibt. Wenn es Sie interessiert, suche ich das Papier.
Robin Kothari
2
@Emil: domotorps Kommentar war eine Antwort auf eine Verwirrung, die ich hatte. Aber es war ein Missverständnis meinerseits, also habe ich den Kommentar gelöscht. Ich denke, die Eingabe muss eine einzelne natürliche Zahl sein, die nichts codieren sollte.
Robin Kothari
8
@domotorp: Das NP-vollständige Problem, das ich meinte, ist, wenn a,b,cN , festzustellen, ob ax2+byc=0 eine Lösung x,yN . Eine andere Variante ist, wenn a,b,c , festzustellen, ob xc so dass . (Das Ergebnis stammt von dx.doi.org/10.1145/800113.803627 .)x2a(modb)
Emil Jeřábek unterstützt Monica
3
Warum ist die Antwort auf diese Frage nicht offensichtlich NEIN ? Jedes NP-harte Problem hat Instanzen, die eine Boolesche Schaltung "codieren"; Das bedeutet wohl, NP-hart zu sein!
Jeffs
2
@domotorp: Vielleicht ist ein anderer guter "natürlicher" Kandidat das Problem, die minimalen Additionsketten einer einzelnen gegebenen Zahl zu finden. : aus der Anzahl der minimalen Additionsketten : "... Das Problem, eine minimale Additionskette für eine Menge zu finden von Zahlen ist NP-vollständig Dies bedeutet nicht, dass manchmal behauptet wird, dass das Finden einer minimalen Additionskette für NP-vollständig ist. Wir können jedoch leicht schließen, dass das Problem des Findens aller minimalen Additionsketten für eine Zahl ist NP-complete ... "m n nnmnn
Marzio De Biasi

Antworten:

17

Dieses Problem hat eine Variation mit einer einzelnen Ganzzahleingabe:

Hat einen Divisor genau zwischen seinen beiden größten Primfaktoren?n

Die Idee ist, die gleiche zufällige Reduktion aus der in der oberen Antwort auf die verknüpfte Frage beschriebenen Teilmengensumme zu verwenden, wobei jedoch der Zielbereich als die beiden größten Primzahlen codiert wird, anstatt separat angegeben zu werden. Die Definition sieht natürlich aus, obwohl es sich nur um eine verdeckte Paarungsfunktion handelt.

Hier ist eine andere Variante desselben Problems mit einer ähnlichen Reduzierung des Partitionsproblems:

Ist das Produkt zweier Ganzzahlen, die sich um weniger als n 1 unterscheidenn ?n14

In beiden Reduktionen "tarnen" wir eine Reihe von ganzen Zahlen, indem wir in der Nähe befindliche Primzahlen finden und ihr Produkt entnehmen. Wenn dies in polynomialer Zeit möglich ist, sind diese Probleme NP-vollständig.

Ich denke, es ist aufschlussreich, diese Beispiele zusammen mit Mahaneys Theorem zu betrachten : Wenn und wir nahegelegene Primzahlen finden, dann sind diese Mengen nicht spärlich. Es ist befriedigend, eine rein arithmetische Aussage aus der Komplexitätstheorie zu erhalten (auch wenn sie nur mutmaßlich ist und sich auf andere Weise leicht beweisen lässt).PNP

Dan Brumleve
quelle
Was meinst du mit 'wenn P ≠ NP und wir Primzahlen in der Nähe finden können'?
T ....
1
@ao., siehe Peter Shors Antwort, in der die Reduzierung beschrieben wird. Um NP-vollständig zu sein, müssen wir in der Lage sein, eine Primzahl mit | zu finden p - n | < n a in time O (p|pn|<na . Ich werde später versuchen, selbst darüber zu berichten. O((logn)k)
Dan Brumleve
Welche Mengen sind nicht dicht?
T ....
33

Basierend auf der Diskussion werde ich dies als Antwort erneut posten.

Wie bewiesen von Manders und Adleman , das folgende Problem NP-vollständig ist : gegebene natürliche Zahlen , festzustellen , ob es eine natürliche Zahl existiert x c derart , daß x 2aa,b,cxc .x2a(modb)

Das Problem kann äquivalent wie folgt angegeben werden: Bestimmen Sie bei , ob das quadratische x istb,cN eine Lösung hat x , y N .x2+byc=0x,yN

(Das Originalpapier gibt das Problem mit an , aber es ist nicht schwer zu erkennen, dass man es auf den Fall a = 1 reduzieren kann.)ax2+byca=1

Emil Jeřábek unterstützt Monica
quelle
10

Hier ist ein vollständiges Problem mit einer einzelnen natürlichen Zahl als Eingabe.NEXP

Das Problem besteht darin, ein n zu kacheln Raster mit einem festen Satz von Kacheln und Einschränkungen für benachbarte Kacheln und Kacheln an der Grenze zu kacheln. All dies ist Teil der Spezifikation des Problems; Es ist nicht Teil der Eingabe. Die Eingabe ist nur die Zahl n . Das Problem ist NEXP- vollständig für eine Auswahl von Kachelregeln, wie in gezeigtn×nnNEXP

D. Gottesman, S. Irani, "Die Quantität und die klassische Komplexität translational invarianter Kachel- und Hamilton-Probleme", Proc. 50. Jahressymp. on Foundations of Computer Science, 95-104 (2009), DOI: 10.1109 / FOCS.2009.22 . Auch arXiv: 0905.2419 .

Das Problem ist auf Seite 5 der arxiv-Version definiert.

Darüber hinaus definieren sie ein ähnliches Problem, das -complete ist, also das Bounded-Error-Quantenanalogon von NEXP . (Das klassische Bounded- Error-Analogon von NEXP ist MA EXP .)QMAEXPNEXPNEXPMAEXP

Robin Kothari
quelle
3
+1, aber es ist ein wenig schwierig zu argumentieren, dass die Zahl auf "natürliche" Weise verwendet wird, da sie die Eingabe für eine bestimmte Turing-Maschine codiert (insbesondere existiert die Kachelung, wenn die Turing-Maschine x akzeptiert , wobei x ist das n- te in einer Aufzählung möglicher Eingabezeichenfolgen. Immer noch ein sehr interessantes Ergebnis. nxxn
mjqxxxx 30.10.12
Ich bin mit mjqxxxx maximal einverstanden.
Domotorp
2

Ich denke, dass Sie mit einer der zeitlich begrenzten Varianten der Kolmogorov-Komplexität ein Problem erstellen können, das nur die binäre Darstellung einer Zahl verwendet und (wie ich finde) wahrscheinlich nicht in P . informell ist es eine entscheidbare Version des Problems "Ist komprimierbar?":n

Problem: Existiert bei eine Turingmaschine M so, dass | M | < l und M auf einem leeren Band geben n in weniger als l 2 Schritten aus, wobei l = log nnM|M|<lMnl2l=logn die Länge der Binärdarstellung von n

Es ist eindeutig in , weil bei n und M M für l 2 Schritte simuliert wird und wenn es anhält, das Ergebnis mit n verglichen wirdNPnMMl2n .

Marzio De Biasi
quelle
Ich denke, dieses Problem basiert auf TM, aber es ist natürlich unmöglich, eine Linie zu ziehen.
Domotorp
Um den Kommentar von domotorp zu verfeinern, würde ich sagen, dass die Tatsache, dass in der Problembeschreibung der Begriff einer Turing-Maschine verwendet werden muss, diese als „natürliches Problem mit natürlichen Zahlen“ ausschließt. (Wenn wir annehmen, dass ein ntaurales Problem über natürliche Zahlen eines ist, dessen allgemeines Format z. B. mit Fermat übereinstimmt , der es studiert hat, ohne eine zu kontrafaktische Geschichte der Mathematik
anzunehmen
2

Unser FOCS'17-Artikel über die kurze Presburger-Arithmetik ist ein Beispiel für ein "natürliches" Problem, das NP-c ist und eine konstante Zahl C von ganzen Zahlen in der Eingabe verwendet, beispielsweise C<220 . Es unterscheidet sich von Manders-Adleman darin, dass die Einschränkungen alle Ungleichungen sind. In Gil Kalais Blogpost finden Sie Hintergrundinformationen.

Igor Pak
quelle
Ich denke, das ist natürlicher als Manders-Adleman. Ist kleiner als Variablen und 10 Ungleichungsbeispiele möglich? 510
T ...
No, 5 variables is the smallest. 10 - not sure. But you can't really have less than 6...
Igor Pak
Is there a reason behind 5 and 6? I mean is it proven that all 4 and finite number of inequalities is in P (likewise all 5 variables and 5 inequalities formulation is in P?)?
T....
Yes. For fewer variables the problem is in P.
Igor Pak
2
Yes. It's all in our paper and Danny Nguyen's thesis. math.ucla.edu/~pak/papers/Nguyen-thesis.pdf
Igor Pak
1

How about the PARTITION problem?

Kevin A. Wortman
quelle
3
No, as the input is not a number but a set.
domotorp
1
So are you asking for problems for which an instance is exactly one natural number? I don't think that's clear in your question, as you ask for "problems with natural inputs" and your example of the Nim game involves four numbers.
Kevin A. Wortman
I am sorry if I was vague in the formulation of the question.
domotorp