Tentamen: Complexiteitstheorie P en NP

Wat is complexiteitsklasse P?

De klasse van beslissingsproblemen die in polynomiale tijd oplosbaar zijn. Dit betekent dat de tijd om het probleem op te lossen een polynoomfunctie is van de grootte van de invoer.

Wat is complexiteitsklasse NP?

De klasse van beslissingsproblemen waarvoor een oplossing in polynomiale tijd kan worden geverifieerd, gegeven een potentiële oplossing. Dit betekent dat, als je een oplossing hebt, je deze snel kunt controleren.

Vul de lege plek in: P staat voor ______.

Polynomiaal.

Waar staat de NP-compleetheid voor?

NP-compleet betekent dat een probleem zowel in NP zit als dat elk probleem in NP in polynomiale tijd kan worden gereduceerd naar dit probleem.

Is P gelijk aan NP?

Onbekend. Dit is een van de grootste open vragen in de theoretische informatica.

Geef een voorbeeld van een NP-compleet probleem.

Het reisverkopersprobleem (TSP) is een voorbeeld. Het vraagt om de kortste route die een verkoper langs een aantal steden moet afleggen.

Wat is een polynomiale tijdscomplexiteit?

Complexiteit die kan worden uitgedrukt als $\displaystyle O(n^k)$, waarbij $\displaystyle n$ de invoergrootte is en $\displaystyle k$ een constante is.

Vergelijk P en NP.

P: Problemen oplosbaar in polynomiale tijd. NP: Problemen met oplossingen die snel geverifieerd kunnen worden.

Wat is een niet-deterministische Turingmachine?

Een theoretisch model dat meerdere paden tegelijk kan verkennen. Het wordt gebruikt om te begrijpen hoe NP-problemen werken.

Wat is een polynomiale reductie?

Een manier om een probleem in NP te transformeren naar een ander probleem in NP, zodat een oplossing van het tweede probleem ook een oplossing voor het eerste probleem biedt.

Geef een voorbeeld van een probleem in P.

Het sorteren van een lijst van getallen met een algoritme zoals mergesort of quicksort is een voorbeeld. Deze algoritmes hebben een tijdcomplexiteit van $\displaystyle O(n imes ext{log}(n))$.

Wat zijn de gevolgen als P gelijk is aan NP?

Als P gelijk is aan NP, dan kunnen veel problemen die nu onoplosbaar lijken, efficiënt worden opgelost. Dit zou enorme gevolgen hebben voor cryptografie, optimalisatie en andere gebieden.

Wat is een herkenningsprobleem?

Een type probleem waarbij je moet bepalen of er een oplossing bestaat voor een gegeven probleem. Herkenningsproblemen zijn vaak NP-compleet.

Wat betekent het dat een probleem NP-hard is?

Een NP-hard probleem is minstens zo moeilijk als het moeilijkste probleem in NP, maar hoeft zelf niet in NP te zitten.

Wat is het verschil tussen NP en NP-hard?

NP: Oplossingen zijn verifieerbaar in polynomiale tijd. NP-hard: Problemen die niet noodzakelijkerwijs binnen NP vallen, maar minstens zo moeilijk zijn.

Wat is een deterministische Turingmachine?

Een deterministische Turingmachine is een theoretisch model van computationele processen. Het volgt een specifieke set regels zonder enige willekeur. Dit betekent dat voor elke stap in de berekening de actie vastligt. - Aanname: elke invoer heeft één uitvoer - Basis voor P-klasse.