Naar inhoud
BetaAI Begrippen

AI-begrippen in gewone taal. Zoek een begrip, blader op letter of filter op onderwerp.

NP

Engels: NP · Ook wel: nondeterministic polynomial time, non-deterministic polynomial time, niet-deterministische polynomiale tijd

In het kort

NP, kort voor niet-deterministisch polynomiaal, is een complexiteitsklasse van ja-nee-problemen in de informatica. Bij een ja-antwoord bestaat een bewijs dat een gewone computer in polynomiale tijd kan controleren: de rekentijd blijft begrensd door een macht van de invoer. Het vinden van dat bewijs mag veel langer duren, waardoor een voorstel soms snel te keuren is en toch moeilijk te vinden blijft.

Waarom is dit belangrijk?

Met NP kunnen onderzoekers rekenvragen indelen en de zwaarste groep aanwijzen, zodat duidelijk wordt waar een algemene snelle methode nog niet bekend is. In de logistiek horen routeplanning en het verdelen van lading daarbij, via het handelsreizigersprobleem en het knapzakprobleem. Voor planners en studenten blijft daardoor onzeker of zulke vragen altijd snel exact oplosbaar zijn, omdat nog niet vaststaat dat elke vraag in NP ook snel te berekenen is.

Zo werkt het in de praktijk

Ontwerpers van elektronica gebruiken problemen uit NP bij het controleren van chips. Een oplosser zoekt of een logische formule waar kan worden. Zo vergelijken zij twee ontwerpen en leggen zij paden op een programmeerbare chip.

Onderzoekers willen weten waarom zulke oplossers veel praktijkgevallen aankunnen. Willekeurige formules en formules uit de cryptografie blijven vaak lastig. Vijay Ganesh en Moshe Vardi zien de oplosser als een systeem dat een bewijs opbouwt.

Een veelgebruikte werkwijze is conflict-driven clause learning, kort CDCL. De oplosser haalt uit een tegenstrijdigheid een nieuwe regel en zoekt daarmee verder. Ontwikkelaars vergelijken zulke oplossers in SAT-wedstrijden.

Bron: en.wikipedia.org

Gecontroleerd op 5 november 2026