In der Kompliziertheitstheorie die Kompliziertheitsklasse ist NP-easy der Satz von Funktionsproblemen, die in der polynomischen Zeit durch eine deterministische Maschine von Turing mit einem Orakel für ein Entscheidungsproblem in NP lösbar sind.

Mit anderen Worten ist ein Problem X NP-easy, wenn, und nur wenn dort ein Problem Y in solchem NP besteht, dass X polynomisch-maliger auf Y reduzierbarer Turing ist. Das bedeutet, dass gegeben ein Orakel für Y, dort ein Algorithmus besteht, der X in der polynomischen Zeit (vielleicht durch das wiederholte Verwenden dieses Orakels) löst.

NP-easy ist ein anderer Name für FP (sieh den Funktionsproblem-Artikel), oder für FΔP (sieh den polynomischen Hierarchie-Artikel).

Ein Beispiel eines NP-easy Problems ist das Problem, eine Liste von Schnuren zu sortieren. Das Entscheidungsproblem "ist Schnur Ein größerer, als Schnur B" in NP ist. Es gibt Algorithmen wie Schnellsortierung, die die Liste mit nur einer polynomischen Zahl von Anrufen zur Vergleich-Routine plus ein polynomischer Betrag der zusätzlichen Arbeit sortieren kann. Deshalb ist das Sortieren NP-easy.

Es gibt auch schwierigere Probleme, die NP-easy sind. Sieh NP-equivalent für ein Beispiel.

Die Definition von NP-Easy verwendet die Verminderung von Turing aber nicht vieleine Verminderung, weil die Antworten auf das Problem Y nur wahr oder FALSCH SIND, aber die Antworten auf das Problem X können allgemeiner sein. Deshalb gibt es keine allgemeine Weise, ein Beispiel X zu einem Beispiel von Y mit derselben Antwort zu übersetzen.

Referenzen