alle ja/nee problemen die opgelost kunnen worden met een deterministische Turingmachine binnen polynomiale tijd.
alle ja/nee problemen die kunnen opgelost worden met een uitvoeringstijd die een veelterm is afhankelijk van de invoerlengte.
string matching: staat p = "rocket" in t = "The rocketry expert is here."? als je voor dit probleem de complexiteit gaat berekenen, zie je dat dit probleem in $$ O(n^2) $$ loopt en dus polynomiaal afhankelijk is van de lengte van het probleem (van p en t)
- alle ja/nee problemen waarbij een uitkomst "ja" geverifieerd kan worden in polynomiale tijd met een deterministische Turing machine.
- alle ja/nee problemen die opgelost kunnen worden in polynomiale tijd met een *non-*deterministische Turing machine.
alle ja/nee problemen waarbij een uitkomst "ja" gecontroleerd kan worden in een uitvoeringstijd die een veelterm is afhankelijk van de invoerlengte.
Traveling Salesman Problem: gegeven een bepaalde graaf van steden en wegen, zoek het kortste pad door elke stad en die terug komt bij de 1e stad. Een oplossing zoeken zal niet binnen veeltermtijd gebeuren, het zoeken van een oplossing is van meer afhankelijk dan de invoer grootte (aantal steden).
Wanneer een oplossing echter gevonden is, is het controleren ervan in veelterm tijd te doen: ga na of elke stad in de gevonden route ligt ( + kijk na of die route de kortste is maar daar ga ik niet op in)
het controleren of elke stad in de gevonden route ligt, is te reduceren/vervormen tot een string matching probleem: zit elk character van "abcd" in de route "acdb"? maw, het controleren van een NP probleem, is een P probleem.
een probleem dat binnen de probleem klasse NP zit EN waarbij elk ander probleem binnen NP naar dit probleem kan vervormd worden in veeltermtijd.
Een NP-complete/NPC probleem moet aan 2 voorwaarden voldoen:
- het probleem is een NP probleem
- elk ander probleem binnen NP kan naar dit probleem omgevormd worden binnen veeltermtijd. Herinner u in een van de eerste lessen van GNA waarbij Dutré aantoonde dat elk probleem ofwel een zoekprobleem is, ofwel een convex hull probleem, dit komt neer op NP completeness.
Subset sum problem en knapsack problem (2 problemen)
Subset sum problem: gegeven een verzameling met getallen, is er een deelverzameling waarbij de som = 0?
Knapsack problem: gegeven een verzameling items, elk met een bepaald gewicht en waarde. Bepaal welk item hoeveel keer in een 'rugzak' gestopt kan worden zodat het gewicht onder een bepaalde grens ligt en de waarde maximaal is.
Er kan nagegaan worden dat beide problemen NP zijn,
- bij het subset sum problem kan in veeltermtijd nagegaan worden indien som deelverzameling = 0
- bij het knapsack problem kan in veeltermtijd nagegaan worden indien sum gewicht < max gewicht
Ook kan gezien worden dat het subset sum problem in zekere zin omgevormd kan worden naar het knapsack problem: het gewicht moet 0 zijn (de som van alle getallen) en de waarde (het aantal getallen) moet maximaal zijn.
Omgekeerd kan ook het knapsack problem naar een subset sum problem omgevormd worden.