Ändert sich die Komplexität stark NP-harter oder -vollständiger Probleme, wenn ihre Eingabe unärkodiert ist?

Ändert sich die Schwierigkeit eines stark NP-harten oder NP-vollständigen Problems (wie hier definiert ), wenn seine Eingabe unär anstatt binär codiert ist?

Welchen Unterschied macht es, wenn die Eingabe eines stark NP-harten Problems unärkodiert ist? Ich meine, wenn ich zum Beispiel das schwach NP-vollständige Knapsack-Problem nehme, ist es NP-vollständig, wenn es binär codiert ist, kann aber in Polynomzeit durch dynamisches Programmieren gelöst werden, wenn es unär codiert ist. Vielleicht hat es einige Implikationen für die Härte höherer Ebenen der polynomiellen Zeiterbschaft?

Gilt der Begriff stark ...- auch für andere Komplexitätsklassen, z. B. höhere Klassen der polynomiellen Zeithierarchie?

Ich habe diese Frage zuvor bei stackoverflow.com gestellt, aber es wurde darauf hingewiesen, dass dies hier angemessener ist.

Eine in Unary codierte Problemgröße von ist Größe N und log N, wenn binär. Wenn die Zeit , ist F ( N ) , dies ist F ( size ) im ersten Fall und F ( 2 size ) im zweiten Fall. Ein für den ersten Fall polynomischer Algorithmus wird für den zweiten wahrscheinlich exponentiell sein. Die Kodierung des Problems kann so die Komplexität eines Algorithmus radikal verändern.$N$$N$$\log N$$F(N)$$F(\text{size})$$F(2^{\text{size}})$

Nein.

Wenn Sie die Codierung der Eingabe ändern, haben Sie die formale Definition des Problems geändert. Dies bedeutet, dass es sich um ein anderes Problem handelt . Die Komplexität des ursprünglichen Problems ändert sich nicht, aus dem gleichen Grund, dass das Zeigen auf ein anderes Licht am Himmel die Masse des Mondes nicht ändert.

Die kurze Antwort lautet: Wenn die Eingabe unär verschlüsselt ist, ist sie länger . Es ist exponentiell länger. Nun hat ein Algorithmus, der in Polynomialzeit in der Größe der Eingabe arbeitet, "genug Zeit", um das Problem zu lösen, nur weil die Eingabe selbst exponentiell länger ist als im ursprünglichen Problem.

Nach der Formulierung, auf die JeffE in seiner Antwort hingewiesen hat, lautet die Antwort ja.

Betrachten Sie das Knapsack- Problem. Es gibt einen Pseudo-Polynom- Algorithmus, bei dem die Laufzeit durch ein Polynom in einer in der Eingabe codierten Zahl begrenzt ist. Da in der unären Codierung die Werte der Länge entsprechen, handelt es sich um einen Polynom-Zeit-Algorithmus für die unäre Version.

Tatsächlich fällt jedes schwach NP-vollständige Problem in diese Kategorie.