| Property |
Value |
| dbo:abstract
|
- In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine fundamentale Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Intuitiv beschrieben, enthält NP die Entscheidungsprobleme, bei denenes für „Ja“-Antworten Beweise gibt, die effizient (in Polynomialzeit) verifiziert werden können.Es kann aber mitunter aufwändig sein, einen solchen Beweis zu finden.Eine alternative Beschreibung von NP ist also die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine bezüglich der Eingabelänge in Polynomialzeit gelöst werden können. Hierbei wird eine Instanz mit „Ja“ beantwortet, wenn mindestens eine der möglichen Berechnungen der nichtdeterministischen Turingmaschine dies tut. Besonders interessant sind Probleme, die vollständig für die Klasse NP sind.NP-vollständige Probleme lassen sich vermutlich nicht effizient lösen. Alle bekannten deterministischen Algorithmen für diese Probleme erfordern exponentiellen Rechenaufwand, und erfahrene Informatiker erwarten, dass es keine effizienteren Algorithmen gibt. Die Bestätigung oder Widerlegung dieser Vermutung ist das P-NP-Problem, eines der wichtigsten offenen Probleme der Informatik.Das vielleicht bekannteste NP-vollständige Problem ist das Problem des Handlungsreisenden. Gelegentlich wird NP als die Klasse der nicht in Polynomialzeit lösbaren Probleme bezeichnet.Hier ist aber Vorsicht geboten: Die Klasse NP definiert lediglich eine obere Schranke für die Komplexität der enthaltenen Probleme und enthält auch alle in Polynomialzeit lösbaren Probleme.Richtig ist, dass NP-schwere Probleme vermutlich nicht in Polynomialzeit gelöst werden können.Es gibt aber NP-schwere Probleme, die selbst nicht in NP liegen, also noch schwerer als NP sind. (de)
- In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine fundamentale Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Intuitiv beschrieben, enthält NP die Entscheidungsprobleme, bei denenes für „Ja“-Antworten Beweise gibt, die effizient (in Polynomialzeit) verifiziert werden können.Es kann aber mitunter aufwändig sein, einen solchen Beweis zu finden.Eine alternative Beschreibung von NP ist also die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine bezüglich der Eingabelänge in Polynomialzeit gelöst werden können. Hierbei wird eine Instanz mit „Ja“ beantwortet, wenn mindestens eine der möglichen Berechnungen der nichtdeterministischen Turingmaschine dies tut. Besonders interessant sind Probleme, die vollständig für die Klasse NP sind.NP-vollständige Probleme lassen sich vermutlich nicht effizient lösen. Alle bekannten deterministischen Algorithmen für diese Probleme erfordern exponentiellen Rechenaufwand, und erfahrene Informatiker erwarten, dass es keine effizienteren Algorithmen gibt. Die Bestätigung oder Widerlegung dieser Vermutung ist das P-NP-Problem, eines der wichtigsten offenen Probleme der Informatik.Das vielleicht bekannteste NP-vollständige Problem ist das Problem des Handlungsreisenden. Gelegentlich wird NP als die Klasse der nicht in Polynomialzeit lösbaren Probleme bezeichnet.Hier ist aber Vorsicht geboten: Die Klasse NP definiert lediglich eine obere Schranke für die Komplexität der enthaltenen Probleme und enthält auch alle in Polynomialzeit lösbaren Probleme.Richtig ist, dass NP-schwere Probleme vermutlich nicht in Polynomialzeit gelöst werden können.Es gibt aber NP-schwere Probleme, die selbst nicht in NP liegen, also noch schwerer als NP sind. (de)
|
| dbo:wikiPageID
| |
| dbo:wikiPageRevisionID
| |
| dct:subject
| |
| rdfs:comment
|
- In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine fundamentale Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Intuitiv beschrieben, enthält NP die Entscheidungsprobleme, bei denenes für „Ja“-Antworten Beweise gibt, die effizient (in Polynomialzeit) verifiziert werden können.Es kann aber mitunter aufwändig sein, einen solchen Beweis zu finden.Eine alternative Beschreibung von NP ist also die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine bezüglich der Eingabelänge in Polynomialzeit gelöst werden können. Hierbei wird eine Instanz mit „Ja“ beantwortet, wenn mindestens eine der möglichen Berechnungen der nichtdeterministischen Turingmaschine dies tut. (de)
- In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine fundamentale Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Intuitiv beschrieben, enthält NP die Entscheidungsprobleme, bei denenes für „Ja“-Antworten Beweise gibt, die effizient (in Polynomialzeit) verifiziert werden können.Es kann aber mitunter aufwändig sein, einen solchen Beweis zu finden.Eine alternative Beschreibung von NP ist also die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine bezüglich der Eingabelänge in Polynomialzeit gelöst werden können. Hierbei wird eine Instanz mit „Ja“ beantwortet, wenn mindestens eine der möglichen Berechnungen der nichtdeterministischen Turingmaschine dies tut. (de)
|
| rdfs:label
|
- NP (Komplexitätsklasse) (de)
- NP (Komplexitätsklasse) (de)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is foaf:primaryTopic
of | |
