Quote (abcmaster @ 16 Aug 2011 18:00)
hatte p-np und endliche automaten etc in theoretische informatik aber ist schon ein jahr her ^^
aber kasiir macht info glaub ich oder?
wenn er n normaler informatik student ist, können mir glaub ich mathematiker wie du eher weiterhelfen^^
soll ich's nochmal n bisschen erläutern?
wikipedia:
Das P-NP-Problem ist ein ungelöstes Problem der Mathematik und theoretischen Informatik. Es stellt die Frage, in welcher Beziehung die beiden Komplexitätsklassen P und NP stehen.
In der Komplexitätstheorie ist P diejenige Komplexitätsklasse, welche die Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind.
NP (nichtdeterministisch polynomielle Zeit) ist in der Informatik eine Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Sie bezeichnet die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine bezüglich der Eingabelänge in Polynomialzeit entschieden werden können.
falls euch der begriff "Turingmaschine" probleme macht, dann denkt ruhig an c++ algorithmen. eine aktion wie c = c+1; oder a = 4*b + c; werden dann einfach mit einer zeiteinheit bewertet
um dann "entscheidungsprobleme" zu lösen, gibt man entweder deterministische oder nicht-deterministische algorithmen an, die das problem lösen
wenn der algorithmuss dann eine polynomielle laufzeit hat (polynomiell in abhängigkeit von der eingabegröße), ist das problem in P bzw. NP
ob es allerdings wirklich einen unterschied gibt, also ob die entscheidungsprobleme aus NP auch in P lösbar sind, also quasi P = NP gilt, oder es entscheidungsprobleme in NP gibt, die nicht in P (also von den nicht-deterministischen turingmaschinen) gelöst werden können, ist seit etwa 40 jahren unklar.