Berechnung der komplexität

hallo,
ich muss in info nen referat über komplexitättheorie halten und wollte da gerne beispele geben: springerproblem und tsp. jetzt weiß ich allerdings nciht wie ich vor allem nicht, wie ich die untere schranke jeweils berechnen soll. zur oberen schranke: beides wird in beispielprogrammen bei mir mit einfachem backtracking gelöst, ohne heuristiken o.ä. ich weiß auch nicht in welche klasse das springerproblem gehört (p oder np?)

ich wäre für antworten mit denkanstößen dankbar

Jester

tjoa schrieb:

hallo,
ich muss in info nen referat über komplexitättheorie halten und wollte da gerne beispele geben: springerproblem und tsp. jetzt weiß ich allerdings nciht wie ich vor allem nicht, wie ich die untere schranke jeweils berechnen soll. zur oberen schranke: beides wird in beispielprogrammen bei mir mit einfachem backtracking gelöst, ohne heuristiken o.ä. ich weiß auch nicht in welche klasse das springerproblem gehört (p oder np?)

Tja, das wirste so wohl auch nicht wirklich in den Griff kriegen. Alles was in P ist, ist auch in NP. Ob aber P != NP gilt oder P=NP ist noch immer nicht geklärt. Insofern wäre es natürlich schön, wenn Du zeigen könntestn, dass das Springerproblem nicht in P liegt, in NP liegt es nämlich sicher und dann hättest Du P!=NP gezeigt. Leider ist es aber (für die meisten) unrealistisch das hinkriegen zu wollen.

Wahrscheinlich willst Du Dich eh mehr mit NP-Vollständigkeit beschäftigen oder? Beweise für die NP-Vollständigkeit lassen sich sicher ne Menge finden im Netz, zumindest was TSP angeht. Allerdings wirst Du mindestens den Satz von Cook glauben müssen, sonst kommste in nem Referat nicht weit.

Jester

http://www.axel-conrad.de/springer/springer.html

Ich hab nur grob drübergeschaut, aber das sieht mir doch so aus, als sei es möglich das Springer-Problem in Polynomialzeit zu lösen.

hi,
ja klar, das mit der unteren schrank für tsp ist müll bzw. utopisch, aber wie sieht es denn damit beim springerproblem aus?
dabei probiere ich doch 8^8 möglichkeiten durch (brute-force für alle möglichkeiten)!? dann ist das doch auch exponentiell und liegt nicht sicher in p also erstmal nur in np. die frage: wie finde ich ne gute untere schranke, also unter n^n?
beim tsp hab ich für die obere schranke: es gibt n!/2 möglichkeiten für wege und die berechne ich ja auch alle mit meinem algorithmus, wobei n die anzahl der knoten ist. wie drücke ich das jetzt aber als zeitbedarf aus?

du hast auch geschrieben, dass das springerproblem anscheinend in polynomialzeit lösbar sei. warum ist denn das kein beweis dafür, dass p=np ist? beim springerproblem wächst doch die anzahl der möglichkeiten exponentiell mit der seitenlänge oder nciht? (n^n)

Aber schon mal danke für die bisherigen antworten, der link ist sehgr inormativ aber über die komplexitätsberechnung finde ich da nicht viel.

tschuldigung, habe wärend des schriebens des postings wohl zwischen durch an das 8-dame-problem gedacht: die oberen schranken passen dann wohl eher nciht

Jester

Du wirfst da ein paar Sachen durcheinander, und zwar: Laufzeit eines Algorithmus und Komplexität eines Problems.

Grundsätzlich gilt folgendes: Die Komplexität eines Problems ist die Laufzeit des schnellsten Algorithmus, der dieses Problem löst. Und eben nicht die Laufzeit eines beliebigen Algorithmus.

Betrachten wir mal das Sortierproblem. Eingabe ein array mit n Zahlen, Ausgabe ein Array mit den gleichen n Zahlen. Auch hier gibt es n! viele Möglichkeiten.
Trotzdem existieren Algorithmen, die sowas in Polynomialzeit lösen.

Damit ein Problem nicht in P liegt muss man nicht einen Algorithmus angeben, der langsamer ist, sondern man muss zeigen, dass es keinen Algorithmus gibt (garkeinen geben kann!), der das Problem in Polynomialzeit löst. Das ist im allgemeinen bedeutend schwieriger.

Die Schranken, die Du vorgeschlagen hast beschränken zwar die Anzahl der Möglichkeiten, aber es könnte ja auch Algorithmen geben, die noch viel schlauer vorgehen. Ich glaube ich hatte im Netz mal was gefunden, dass das n-Damen-Problem ebenfalls in Linearzeit lösbar ist.