NP

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å

• NP-komplet
• Church-Turing-tesen

Spire Denne artikel om datalogi eller et datalogi-relateret emne er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.