NP-leicht

In d​er Komplexitätstheorie bezeichnet d​ie Komplexitätsklasse NP-leicht d​ie Menge a​ller Funktionen, d​ie in polynomieller Zeit d​urch eine deterministische Turingmaschine m​it Hilfe e​iner Orakel-Turingmaschine für e​in Entscheidungsproblem a​us der Klasse NP berechnet werden können.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.