Warum nicht die unäre Darstellung von Zahlen in numerischen Algorithmen nehmen?

15

Ein Pseudo-Polynom-Zeit-Algorithmus ist ein Algorithmus, der eine Polynomlaufzeit für den Eingabewert (Größe), aber eine Exponentiallaufzeit für die Eingabegröße (Anzahl der Bits) aufweist.

Zum Beispiel erfordert das Testen, ob eine Zahl eine Primzahl ist oder nicht, eine Schleife durch die Zahlen von 2 bis und prüft, ob mod Null ist oder nicht. Wenn der Mod O (1) -Zeit benötigt, ist die Gesamtzeitkomplexität O (n).nn1n i

Aber wenn wir die Anzahl der erforderlichen Bits zum Schreiben der Eingabe sein lassen, dann ist x = log n (binär), also und die Laufzeit des Problems ist O ( ), was exponentiell ist.xx=lognn=2x2x

Meine Frage ist, wenn wir die unäre Darstellung von Eingabe , dann ist immer und dann ist die Pseudo-Polynomzeit gleich der Komplexität der Polynomzeit. Warum machen wir das nie?nx=n

Da es ferner einen Pseudo-Polynom-Zeitalgorithmus für den Rucksack gibt, wird der Rucksack, indem wird, als Ergebnis P = NP polynomisch seinx=n

M ama D
quelle
3
Eigentlich machen wir das nicht so oft. Aus den gleichen Gründen beschäftigen wir uns normalerweise nicht mit unären Sprachen, aber es gibt viele interessante Ergebnisse im Zusammenhang mit diesen Tieren. Hast du es dir angesehen?
André Souza Lemos
2
Ja, wenn Sie den Unterschied zwischen Größe und Größe beseitigen, verlieren Sie alle Konzepte, die auf diesem Unterschied beruhen.
André Souza Lemos
7
Weil es den Dämon in ein schönes Kleid setzt. Es macht nichts schneller, es macht nur die "Laufzeitkomplexität" bedeutungslos.
Raphael
4
@Drupalist Es ist eigentlich nicht bekannt, dass das unäre Rucksackproblem NP-vollständig ist, da die normale Reduktion auf das Rucksackproblem davon ausgeht, dass Zahlen in Binärform geschrieben sind. Wenn Sie versuchen, die Standardreduktion durchzuführen, aber die Zahlen unär schreiben, kann die Reduktion nicht in Polynomzeit berechnet werden. Infolgedessen würde das unäre Rucksackproblem, das in Polynomzeit lösbar ist, nicht bedeuten, dass P = NP ist.
Templatetypedef
2
Möglicherweise möchten Sie andere Antworten mit dem Tag Pseudo-Polynom überprüfen, insbesondere diese .
Raphael

Antworten:

17

Dies bedeutet, dass sich der unäre Rucksack in P befindet. Dies bedeutet nicht, dass sich der Rucksack (mit binär codierten Zahlen) in P befindet.

Rucksack ist bekanntermaßen NP-vollständig. Wenn Sie zeigen würden, dass der Rucksack in P ist, würde dies zeigen, dass P = NP ist.

Sie haben jedoch nicht gezeigt, dass der Rucksack in P enthalten ist. Sie haben gezeigt, dass der unäre Rucksack in P enthalten ist. Es ist jedoch nicht bekannt, dass der unäre Rucksack NP-vollständig ist ). Daher impliziert das Einfügen eines unären Rucksacks in P nicht, dass P = NP ist.


Welches Problem sollte uns mehr interessieren, Rucksack oder unärer Rucksack? Wenn Ihre Motivation auf praktischen Bedenken beruht, hängt die Antwort von der Größe der Zahlen ab, für die Sie das Rucksackproblem lösen möchten: Wenn sie groß sind, interessiert Sie sicherlich mehr der Rucksack als der unäre Rucksack. Wenn Ihre Motivation auf theoretischen Überlegungen beruht, ist der Rucksack wahrscheinlich interessanter, weil er uns ein tieferes Verständnis verschafft - es ermöglicht uns, zwischen Größe und Größe zu unterscheiden -, wohingegen der unäre Rucksack uns daran hindert, diese Unterscheidung zu treffen.


So beantworten Sie die folgende Frage zum dynamischen Programmieralgorithmus für das Rucksackproblem:

Ja, derselbe dynamische Programmieralgorithmus kann sowohl auf den Rucksack als auch auf den unären Rucksack angewendet werden. Ihre Laufzeit ist in der Größe der Zahlen polynomisch, in der Länge der Zahlen jedoch exponentiell (nicht polynomisch), wenn sie binär codiert ist. Somit seine Laufzeit ist Polynom in der Länge des Eingangs , wenn die Eingabe in unäre codiert wird , ist aber nicht in der Länge der Eingangs - Polynom , wenn der Eingang in binär codiert ist. Deshalb haben wir nicht diesen dynamischen Programmieralgorithmus betrachten ein Polynom-Algorithmus für einstelligen Ranzen sein, aber nicht betrachten es als ein Polynom-Algorithmus für (binär codiert) Tornister sein.

Denken Sie daran, dass wir sagen, ein Algorithmus läuft in Polynomzeit, wenn seine Laufzeit höchstens ein Polynom der Länge der Eingabe in Bits ist .

DW
quelle
1
Vielen Dank, ich wusste nicht, dass die Komplexitätsklasse von unär und nichtunär desselben Algorithmus unterschiedlich sein kann. Warum kann die dynamische Programmierlösung des Standard-Rucksacks nicht auf einen unären Rucksack angewendet werden, was zu unterschiedlichen Komplexitätsklassen geführt hat? Ich habe Probleme mit dem Verständnis der unären Version von Problemen.
M ama D
@ Drupalist, ich habe meine Antwort bearbeitet und am Ende zwei Absätze hinzugefügt, um diese Frage zu beantworten.
DW
Vielen Dank, von dem, was ich verstehe, ist der Unterschied zwischen der Eingabegröße und ihrer Größe der Grund für die Unterscheidung zwischen Polynom und Pseudo-Polynom. Durch die Verwendung einer unären Darstellung habe ich versucht, diesen Unterschied zu beseitigen. Wenn wir den Rucksack vergessen und zurück zur Zahl Algorithmen, würde ich gerne wissen, durch Setzen von was die Interpretation von Polynom und Pseudo-Polynom sein wird? Nochmals x=n
vielen
@ Drupalist, ich bin mir nicht ganz sicher, was Sie mit meinen , daher weiß ich nicht, wie ich antworten soll. An dieser Stelle würde ich vorschlagen, dass es am besten ist, eine neue (in sich geschlossene) Frage zu stellen (und alle Variablen in dieser Frage zu definieren). Diese Plattform ist nicht so gut für Folgefragen oder Hin- und Rückfragen: Wir müssen am besten eine neue Frage stellen, basierend auf dem, was Sie aus den Antworten auf diese Frage gelernt haben. x=n
DW
1
@ NikosM., OK, verstanden. Danke für die Rückmeldung. Persönlich glaube ich nicht, dass diese Aussage falsch ist, also werde ich sie so lassen, wie sie ist. (Meine Argumentation: Die Länge der Eingabe hängt von der Wahl der Darstellung ab, daher glaube ich nicht, dass sie irgendetwas widerspricht, das Sie geschrieben haben.) Es ist jedoch durchaus möglich, dass meine Perspektive zu eng ist oder dass eine detailliertere Erklärung oder Erklärung vorliegt Eine andere Perspektive könnte einen Mehrwert schaffen. Fühlen Sie sich frei, eine zusätzliche Antwort zu schreiben oder eine Änderung vorzuschlagen, wenn Sie der Meinung sind, dass dieser Punkt klarer sein könnte.
DW
6

Ich würde der Antwort von DW noch eine Kleinigkeit hinzufügen:

Ich habe Leute gesehen, die denken, dass, weil der unäre Knapsack in P ist, wir ihn anstelle des Knapsacks verwenden können, dessen beste aktuelle Algorithmen exponentielle Zeit haben.

Sei die Eingabe und k und betrachte den dynamischen Programmieralgorithmus für Knapsack und unären Knapsack. Die Laufzeit für beide von ihnen sind O ( n k ) . Es ist die gleiche Laufzeit. Dh wenn Sie eine Eingabe haben, spielt es keine Rolle, ob Sie die dynamische Programmierung für unary Knapsack oder die dynamische Programmierung für Knapsack verwenden. Beide benötigen (ungefähr) dieselbe Zeit, um die Probleminstanz zu lösen. Theoretisch kann man überall, wo man eins benutzt, auch das andere benutzen. Sie müssen nur Zahlen von unär nach binär konvertieren und umgekehrt.W={w1,,wn}kO(nk)

Worum geht es also bei der Definition der Komplexität von Algorithmen in Abhängigkeit von der Größe der Eingaben? Warum geben Sie sie nicht immer als ?O(nk)

Wenn Ihnen ein Problem im Alleingang wichtig ist, können Sie dies tun. Tatsächlich ist es das, was Menschen in Algorithmen oft tun. Die Komplexität von Grafikalgorithmen wird häufig durch die Anzahl der Eckpunkte und die Anzahl der Kanten ausgedrückt, nicht durch die Größe der Zeichenfolge, die sie codiert.

Dies ist jedoch nur dann der Fall, wenn es sich um ein isoliertes Problem handelt. Dies ist nicht sinnvoll, wenn wir Probleme mit verschiedenen Arten von Eingaben haben. Bei Diagrammen können wir über die Laufzeit in Bezug auf die Anzahl der Eckpunkte und Kanten sprechen. Bei Knapsack können wir über die Anzahl der Artikel und die Größe des Knapsacks sprechen. Aber was ist, wenn wir über beides sprechen wollen? Zum Beispiel, wenn wir die Anzahl der Probleme reduzieren oder eine Klasse von Problemen diskutieren möchten, die beliebige Probleme enthält, nicht nur solche mit einem Graphen als Eingabe. Wir brauchen einen universellen Parameter von Eingaben. Eine Eingabe ist im Allgemeinen nur eine Zeichenfolge. Wir interpretieren ihre Symbole als unäre Zahlen, Binärzahlen, Diagramme usw. Um eine allgemeine Theorie der Komplexität von Algorithmen und Problemen zu entwickeln, benötigen wir einen allgemeinen Parameter für Eingaben. Die Größe der Eingabe ist eine naheliegende Wahl und es stellt sich heraus, dass sie robust genug ist, um darauf eine vernünftige Theorie aufzubauen. Es ist nicht die einzige Möglichkeit. Für einen Künstlichen können wir eine Theorie aufbauen, die darauf basiert auf die Größe der Eingabe. Es wird gut funktionieren.2

Jetzt entscheiden wir uns, die Größe als universellen Parameter für Eingaben zu verwenden. Sie zwingt uns, über die Codierung von Objekten in Form von Zeichenfolgen nachzudenken. Es gibt verschiedene Möglichkeiten, sie zu codieren, und sie können unterschiedliche Größen haben. (Sie machen auch verschiedene Dinge leicht / schwer.) Im Sinne einer allgemeinen Theorie von Algorithmen wird es wichtig, ob wir die eingegebene Zahl in unär oder binär codieren. Wenn wir unary verwenden und die Größe von 100 ist, erhalten wir die größte Zahl von 100 . Wenn wir binäres k verwenden, kann es bis zu 2 100 - 1 groß sein . Wenn wir also über die Laufzeit der Lösung von Knapsack-Problemen sprechen, bei denen die Größe von kk100100k21001kist 100 ergeben sich zwei sehr unterschiedliche Situationen: In einem Fall kümmern wir uns nur um Eingaben, bei denen höchstens 100 ist. In dem anderen Fall kümmern wir uns um Eingaben, die bis zu 2 100 - 1 groß sein können .k21001

Angenommen, ich möchte sehen, ob ich SAT in Polynomialzeit auf Knapsack reduzieren kann. Angenommen, die Eingabeformel für SAT hat die Größe . Dann kann ich nur eine Eingabe für Knapsack erstellen, die ein Größenpolynom in n hat . Angenommen, p ( n ) ist die Größe der Eingabe für Knapsack, die ich erstelle. Wenn ich unary benutze, kann ich k nur so setzen , dass es höchstens p ( n ) ist . Wenn ich binär verwende, kann ich k auf 2 p ( n ) - 1 setzen . Es stellt sich heraus, dass ich k setzen mussnnp(n)kp(n)k2p(n)1kziemlich groß, um SAT auf Knapsack reduzieren zu können. Daher funktioniert unary Knapsack nicht, um SAT darauf zu reduzieren. Binary Knapsack würde jedoch funktionieren. Wir werden in der Lage sein, eine Knapsack-Instanz mit viel größerem zu erstellen, wenn wir Binärdateien verwenden.k

Eine andere Möglichkeit, darüber nachzudenken: Angenommen, Sie haben eine Black Box, die den unären Knapsack löst, und eine andere, die den Knapsack löst. Angenommen, Sie haben Zeit, einen Bit-Eingang für die Blackbox zu schreiben . Welche der Blackboxen ist leistungsstärker? Offensichtlich derjenige, der binäre Codierung verwendet. Wir können es verwenden , um Knapsack Probleme zu lösen , die exponentiell größer haben k , um Probleme zu vergleichen , dass die einstellige Knapsack Blackbox lösen kann.nk

Kaveh
quelle
Vielen Dank, noch eine Frage: Konvertieren Sie die Eingabe in ihre unäre Darstellung. Was passiert mit dem Problem, zu bestimmen, ob eine Zahl eine Primzahl ist oder nicht? Dieses Problem ist polynomial, basierend auf der Eingangsgröße, aber exponentiell, basierend auf den Eingangsbits (wie ich in der Frage ausgeführt habe). Wird diese Konvertierung etwas besser machen?
M ama D
nO(n)nb=210241210241210241
Kaveh
schöne Klarstellung, aber werfen Sie einen Blick auf meinen Kommentar unter der Antwort der DW, die auf diesen Beitrag bezogen ist
Nikos M.
2

Kurz und einfach, ich zeige Ihnen warum.

Teinlly

x = input integer

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

Notice that the above algorithm is polynomial of the numeric value of x. It will take x amount of steps in the loop. But when it comes to bit-size its actually Ö(2n).

Suppose, I make a small edit to the code that will take in Teinlly/Uneinry. Es wird jetzt seinÖ(n) Zeit in Wert und Länge der Eingabe x.

x = input tallies

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

Durch die Eingabedarstellung wird der Code nicht schneller ausgeführt. Auch wenn der 2. Algorithmus wirklich Polyzeit ist. Es ist nicht sehr praktisch, um die Faktoren für RSA zu finden.

Travis Wells
quelle
Nice example, thanks
M a m a D