NP

Fra Wikipedia, den frie encyklopædi

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

organisation