Sind NP-Proofs auf Polynomlänge beschränkt?

Question

In der Rechenkomplexitätstheorie ist die NP (Nondeterministische Polynomzeit) eine Komplexitätsklasse, die zur Klassifizierung von Entscheidungsproblemen verwendet wird.NP ist die Reihe von Entscheidungs-Problemen, für die die Probleminstanzen, in denen die Antwort "Ja" ist, Beweise in der Polynomzeit durch eine deterministische Turierungsmaschine überprüfbar ist.

Die Proofs für ein NP-Entscheidungsproblem werden bei der Polynomialzeit überprüft.

bedeutet dies, dass die Beweise auf den meisten Polynomlänge sind?

"Nun, Sie müssen den ganzen Eingang lesen. Wenn der Eingang länger als Polynom ist, ist die Zeit größer als das Polynom."

das Entscheidungsproblem "ist das erste Bit des Eingangs A 0?"kann in konstanter Zeit und Raum gelöst werden - ohne den gesamten Eingang zu lesen.

Daher gibt es vielleicht ein paar NP-Problem, die länger als die Polynomlänge sind, sondern in der Polynomzeit überprüft werden.

Answer 1

das Entscheidungsproblem "ist das erste Bit des Eingangs A 0?"kann in konstanter Zeit und Raum gelöst werden - ohne den gesamten Eingang zu lesen.

In Anbetracht dessen, dass ein Turing-Maschinenkopf nach rechts einen Schritt nach rechts bewegt, kann ein Turing-Maschinenkopf nur eine Polynommenge des Beweises in der Polynomzeit lesen.

Während Sie Proosis definieren könnten, um eine Polynomlänge zu überschreiten, könnte nur ein Polynompräfix des Beweises in der Polynomzeit gelesen werden, vorausgesetzt, der Kopf startet an der Zelle 0 und kann sich in einer Zeiteinheit an der maximalen Zelle nach rechts bewegen.

Answer 2

Ein Nachweis von "Ja" -Tinstanz bedeutet, eine Lösung bereitzustellen.Die Bereitstellung einer Lösung bereitstellt einen gültigen Eingang.Nach Definition kann es in Zeit- und Raumpolynom relativ an den Eingang überprüft werden, oder es ist kein Problem in NP.

Es ist unbekannt, ob alle Beweise für "NEIN" -Stüftungszeiten in Polynomialzeit und Raum (den Unterschied zwischen NP und CO-NP) überprüfbar sind.

Um die Frage genau zu beantworten, ist der Nachweis einer "Ja"-Instanz der Eingabewert.Sie können nicht sagen, dass der Eingang eine Polynomlänge aufweist, da beim Vergleich mit der Eingabegröße Polynom verwendet wird.Daher ist die Frage aufgrund des Wortes "Polynom" sinnlos.Wenn Sie wirklich ein Polynom irgendwo wollen, kann die Größe des Beweises relativ zum Eingang als lineare Funktion f (x)= Axt + B definiert werden, wobei a= 1 und b= 0, die mit f (x) vereinfacht werden können= x, weil die Größe des Eingangs gleich selbst ist.