NP

Fra Wikipedia, den frie encyklopædi
Spring til navigation Spring til søgning

Inden for kompleksitetsteori er NP (eng: Non-deterministic Polynomial time, "ikke-deterministisk polynomiel tid") den mængde af beslutningsproblemer der kan løses i polynomiel tid på en nondeterministisk Turingmaskine. Tilsvarende er det mængden af problemer hvis løsninger kan blive verificeret af en deterministisk turingmaskine i polynomiel tid.

Se også[redigér | redigér wikikode]

ProgrammeringStub
Denne artikel om datalogi eller et datalogi-relateret emne er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.