Woher wissen Sie, ob k für O (n^k) in der Subsetsumme konstant ist?

Question

Subset-Summenproblem: Gegeben eine Reihe von Zahlen S und eine Zielnummer, sagen wir 0. Ziel ist es, eine Untermenge S’ von S so zu finden, dass sich die darin enthaltenen Elemente zu 0 addieren. Ich habe gehört, dass dieses Problem polynomial wird, wenn die Größe S’ gegeben ist.
Zum Beispiel, wenn Sie einen Hinweis haben, dass 3 Elemente summieren sich zu 0 können wir Komplexität O(n^3) kommen.

Die Klasse P besteht aus solchen Problemen, die in polynomieller Zeit lösbar sind. Zum Beispiel könnten sie in O(n^k) für einige Konstante k gelöst werden, wobei n die Größe des Eingangs ist. (n^k) bezeichnet die Anzahl von Teilmengen der Größe k von [n]; oder, äquivalent, die Anzahl der Arten, in denen wir k verschiedene Elemente aus einem n -Element auswählen können. Mit n Elementen; Eine k -Untergruppe einer Menge ist eine Teilmenge mit k Elementen. Geben Sie also an, dass es einen Algorithmus in Polynomialzeit gibt, der k -subset findet, oder die -subset, die zu 0 von n Elemente. Ich meine, wenn k eine Eingabe des Algorithmus ist, so dass k auch größer als 3 sein kann. Können wir sagen, k ist konstant oder was?

Answer 1

Wenn die Laufzeit eines Algorithmus für ein Problem mit einer Eingabe von O(n^k) begrenzt wird, hängt es von verschiedenen Dingen ab, ob diese Laufzeitgrenze als polynomial, pseudo-polynom oder keine davon betrachtet wird. Wenn k eine spezifische Konstante wie k=3 ist, ist das gebundene Polynom. Wenn k Teil der Eingabe ist, ist die Laufzeitgrenze nicht betrachtet polynomiell begrenzt.

Das Konzept der Laufzeitgrenzen ist kurz erklärt here; Beachten Sie jedoch, dass die informelle Verwendung des Begriffs "polynomial runtime bound" in der Regel etwas schlampig ist. Im genauesten Sinne kann ein Algorithmus A ein Problem lösen P eine Laufzeitgrenze haben, die polynomiell in der Kodierungslänge seines Eingangs gebunden ist. Dies bedeutet, dass die Grenze auch in Bezug auf die spezifische Codierung von Instanzen der P für A zu sehen ist.

Darüber hinaus, wie in der Regel eine binäre Codierung von Zahlen für Algorithmen verwendet wird, können die codierten Zahlen in ihrer Kodierungslänge exponentiell wachsen. Wenn A eine Laufzeitgrenze hat, die in einem numerischen Wert seiner Eingabe polynomial begrenzt ist, aber nicht in der Kodierungslänge der Eingabe begrenzt ist, wird die Grenze als Pseudopolynom bezeichnet, wie kurz here.

Ich hoffe, dass dies hilft, sind die spezifischen Details in informellen Erklärungen in der Regel ein wenig ungenau.