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

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,c\in \mathbb N,$$ax^2+by-c=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.

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 $n$ ?$n^{\frac{1}{4}}$

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).$P \ne NP$

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 2 ≡ $a,b,c$$x\le c$ .$x^2\equiv a\pmod b$

Das Problem kann äquivalent wie folgt angegeben werden: Bestimmen Sie bei , ob das quadratische $b,c\in\mathbb N$ eine Lösung hat x , y ∈ N .$x^2+by-c=0$$x,y\in\mathbb N$

(Das Originalpapier gibt das Problem mit an , aber es ist nicht schwer zu erkennen, dass man es auf den Fall a = 1 reduzieren kann.)$ax^2+by-c$$a=1$

Hier ist ein vollständiges Problem mit einer einzelnen natürlichen Zahl als Eingabe.$\text{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 gezeigt$n \times n$$n$$\text{NEXP}$

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 .)$\text{QMA}_\text{EXP}$$\text{NEXP}$$\text{NEXP}$$\text{MA}_\text{EXP}$

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 $\mathsf{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 n$n$$M$$|M| < l$$M$$n$$l^2$$l = \lceil \log{n} \rceil$ 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 wird$\mathsf{NP}$$n$$M$$M$$l^2$$n$ .

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.

How about the PARTITION problem?