Inhoudsopgave:
- Definitie - Wat betekent Non-Deterministic Polynomial Time (NP)?
- Techopedia verklaart Non-Deterministic Polynomial Time (NP)
Definitie - Wat betekent Non-Deterministic Polynomial Time (NP)?
Niet-deterministische polynoomtijd (NP) is eigenlijk een marker die wordt gebruikt om te wijzen op een reeks problemen en grenzen van de mogelijkheden van bepaalde typen computers. NP verwijst naar de set problemen die in polynoomtijd kan worden opgelost door een niet-deterministische Turing-machine.
Techopedia verklaart Non-Deterministic Polynomial Time (NP)
Niet-deterministische polynoomtijd is gebaseerd op de uitdrukking "polynoomtijd", die verwijst naar of een algoritme kan presteren binnen bepaalde grenzen die relevant zijn voor snelheid. Polynomiale tijd ontstond als een manier om te praten over de haalbaarheid van algoritmewerk en ontwikkeling.
Als er een probleem is in de niet-deterministische polynoomtijd, kan de niet-deterministische Turing-machine eerst naar de oplossing raden en vervolgens een verifieerbaar algoritme uitvoeren dat zal bevestigen of die schatting correct was of niet. Op verificatie gebaseerde definitie- of machinedefinitieprogramma's zullen in wezen de aanvankelijke keuzes van de niet-deterministische Turing-machine testen om de resultaten te verifiëren.
Dit alles is een zeer theoretische computerstructuur. Hoewel machinaal leren steeds verder is gegaan in het overstijgen van deterministische systemen, staat het idee om niet-deterministische keuzes te verifiëren nog in de kinderschoenen. Kijk voor meer ontwikkeling op deze grens van computing.