NP (kompleksitet)
From Wikipedia, the free encyclopedia
NP er ei kompleksitetsklasse som beskriver beslutningsproblemer. Det finnes flere definisjoner hvor alle er like gyldige. En definisjon på det er at ei løsning skal kunne verifiseres i polynomiell tid. Sagt annerledes vil det si at det finnes ei deterministisk turingmaskin som kan bekrefte at det er en del av språket i polynomiell tid. Språket beskrives som problemet. En annen definisjon på det er at NP er mengda over alle beslutningsproblemer som kan løses av ei ikke-deterministisk turingmaskin som kjører i polynomiell tid. Disse to nevnte definisjonene er bevist er ekvivalente.