NP-Vollständig

[Eisbrecher99]

Hi,

meine Frage geht an Informatiker: Sind Sortieralgorithmen (Quicksort, Mergesort, etc.) immer bzw. überhaupt NP-vollständig?

Ich hatte diese Frage in einer Klausur und mich lässt die Frage nicht in Ruhe bzw. meine Kumpels davon sowieso keine Ahnung.


Danke!

 

[Sondai]

Sortieren kann man in O(N^2) mit BubbleSort, daher definitiv nicht NP vollständig
außer natürlich irgendwer beweist mal P=NP

Edit:

Man kann natürlich Sorts entwerfen die nicht in Polynomialzeit laufen, z.B. BogoSort

 

[Eisbrecher99]

Gut, dann lag ich mit "nein ankreuzen" richtig. Ich hatte zwar schon mal Automatentheorie (nur ein Exkurs in A&D), aber war mir da nicht mehr sicher.

 

[asdfman]

Wenn du da schon die Antwort raten musst, sieht das wohl nicht so rosig für dich aus.

 

[maxwell-cs]

Die Frage zu stellen, ob Sortieralgorithmen NP-vollständig sind, macht keinen Sinn, weil NP-Vollständigkeit eine Eigenschaft von Problemen (oder besser: Sprachen) ist, nicht die Eigenschaft von Algorithmen.

 

[Eisbrecher99]

Wenn du da schon die Antwort raten musst, sieht das wohl nicht so rosig für dich aus.

Noch nicht gemerkt, dass "(richtig) Raten" ein fester Bestandteil in manchen Teilen der Informatik ist? Btw das war sowieso die einzigste Frage zu NP in der Klausur und wegen dem einen Punkt falle ich nicht durch.

Danke an die anderen, die mir das trotzdem erläutert haben.