Eine Frage aus den Gprots lautet:

"Was hat man davon, wenn man weiss, dass ein Problem in NP liegt?"

eigentlich doch gar nichts, oder? Liegen nicht alle Probleme in NP?

Dazu gibt's 'nen recht guten Artikel in der Wikipedia.

netter Artikel, hilft mir aber leider nicht weiter.

Liegen nicht alle Probleme in NP?

Antwort: Nein, es liegen nicht alle Probleme in NP.
Gegenfrage: Wofür, meinst Du, steht der Name "NP"?

Liegen nicht alle Probleme in NP?

Ganz und garnicht! Wie kommst du darauf?

Das sind nur die Probleme, die sich in polynomieller
Zeit mit einer NTM lösen lassen. Quantitativ gesehen
ist NP nur ein sehr kleiner Teil der Menge aller
Sprachen.

Allgemein gilt sogar: für jede (entsprechend
konstruierbare) Zeit- oder Platzschranke gibt es ein
Problem, das sich innerhalb dieser Zeit bzw. mit soviel
Platz nicht lösen läßt. (Die Konstruktion des Problems
geht mit Diagonalisierung, kann ich mal posten, wenn du
willst).

Ein konkretes Beispiel für ein Problem, das nicht
in NP ist (aber noch entscheidbar ist), ist das
Erreichbarkeitsproblem für Petrinetze.

Eine Frage aus den Gprots lautet:

"Was hat man davon, wenn man weiss, dass ein Problem in NP liegt?"

Hm, da kann man jetzt im Prinzip alle Eigenschaften
von Problemen in NP nennen [img]http://www.fb18.de/gfx/28.gif[/img]
Z.B. kann man es in exponentieller Zeit und
polynomiellem Platz mit einer DTM lösen. Und man kann
es reduzieren auf eins der vielen NP-vollständigen
Probleme.

Gegenfrage: Wofür, meinst Du, steht der Name "NP"?

Für die Klasse der Sprachen, die nichtdeterministisch in polynomieller Zeit lösbar sind.

natürlich meinte ich nur alle entscheidbaren probleme.

Und dass es da auch welche gibt die nicht in NP liegen wurde im Skript nicht erwähnt. Hätte man sich vielleicht denken können, denn sonst wäre es bestimmt erwähnt gewesen, wenn NP = REC.

Danke für die Aufklärung