Complexiteit van berekeningen

Logica in actie H O O F D S T U K 7

Complexiteit van berekeningen We hebben nu al een paar keer gezien dat logica nauw verbonden is met processen die informatie bewerken en overdragen. Het proces bij uitstek met deze informatieve functie is rekenen, en daarom gaan we deze connec‐ tie in dit hoofdstuk eens wat preciezer aan het licht brengen. Niet alleen omdat het onderwerp praktisch van belang is in de informatietechnologie, maar ook omdat dit samenhangt met diepe vragen over complexiteit van processen van de meest uiteenlopende aard. Redeneren en rekenen liggen dicht bij elkaar. De twintigste‐eeuwse contac‐ ten tussen logica en informatica gaan terug op een oudere historische traditie van redeneermachines. Zo werken de digitale circuits van een moderne computer in wezen volgens de negentiende‐eeuwse propositie‐ logica van George Boole. Maar naast dit rekenaspect is er nog een tweede kant aan het contact tussen logica en informatica. De logische talen die we gezien hebben geven manieren om diverse soorten van informatie exact uit te drukken: propositioneel, met kwantoren, en modaal (en er zijn nog vele andere mogelijkheden). Daarmee wordt die informatie voor berekening vatbaar. In dit hoofdstuk staat dat genre van berekening centraal. In de informatica gaat het om het juiste samenspel tussen de geschikte weergave of representatie van informatie (in getalstructuren, gegevens‐ banken, of andere vormen) en efficiënte berekening met die gegevens, met andere woorden om de interactie tussen, in het Engels: ‘representation + computation’. En in ons cognitief gedrag vindt een vergelijkbaar samenspel plaats van informatieverwerking met een beperkte hoeveelheid tijd en aandacht. Deze balans kan men goed bestuderen in het gedrag van logische systemen, die een evenwicht moeten vinden tussen logische uitdrukkingskracht en rekencomplexiteit. In het algemeen geldt: hoe rijker de taal, hoe moeilijker het rekenproces voor de centrale logische taken. De bedoeling van dit hoofdstuk is om enig inzicht te geven in deze balans, die vooral typerend is voor logische systemen die ontwikkeld zijn in de buurt van de informatica. In paragraaf 7.1 introduceren we de relevante logische taken: bewijzen, vervullen, evalueren en vergelijken. In de paragrafen 7.2 en 7.3 geven we

1

Logica in actie / Hoofdstuk 7 Complexiteit van berekeningen

enige voorbeelden van de complexiteit van taken in de standaard logische systemen die we gezien hebben. 7.1 Bewijzen, vervullen, evalueren en vergelijken In dit boek zijn heel uiteenlopende logische taken besproken. Het bereke‐ nen van een waarheidswaarde van een formule in een gegeven model is zo’n taak, maar ook het vinden van een model voor een gegeven stel for‐ mules. We zetten een aantal van deze taken nog eens iets uitvoeriger op een rij. Om te beginnen hebben we bewijstaken. Bewijstaken Veel theoretische en praktische problemen komen erop neer dat bepaald (theorem proving) moet worden of een bewering uit een andere volgt. We kunnen dit bijvoor‐ beeld zien bij het automatisch vinden van wiskundige stellingen die volgen uit gegeven axioma’s. Zo kunnen we een bewijs van de stelling van Pytha‐ goras (hoofdstuk 1) in principe mechanisch vinden gegeven een aantal basisaannames (de postulaten van Euclides) en de afleidingsregel ‘modus ponens’ (ϕ, ϕ → ψ ⇒ ψ). Dit soort logische geldigheidsvragen wordt gesteld binnen het kader van een formeel bewijssysteem en de gangbare term hiervoor is stellingbewijzen (in het Engels: ‘theorem proving’). Aan de complexiteit van bewijzen besteden we geen aandacht, behoudens een voorbeeld. VOORBEELD 7.1 Als p bekend is dan kunnen we met twee implicaties p → q en q → r, en de ‘modus ponens’‐regel bewijzen dat r. Eerst volgt uit p en p → q dat q, en uit q en q → r volgt dan r. Dat zijn maar twee stappen, lekker snel dus en niet zo complex. Een probleem in zo’n bewijs is dat q niet voorkomt in de aan‐ name p en ook niet in de te bewijzen conclusie r, en dat het daarom toch heel complex kan worden, namelijk omdat we uit meerdere beschikbare implicaties nu juist p → q en q → r moeten selecteren, en niet twee van tien‐ duizenden andere beschikbare implicaties p → q1, p → q2, ... De complexiteit van bewijzen heeft dus niet alleen te maken met de lengte van het bewijs dat we uiteindelijk vinden, maar ook (en zelfs vooral) met de duur van de zoektocht naar zo’n bewijs. Een ander kort bewijs is dat van p ∧ r ⇒ p ∨ q: uit p ∧ r volgt p, en uit p volgt de zwakkere disjunctie p ∨ q. In dit bewijs is de tussenstap p een deelformu‐ le van het uitgangspunt en een deelformule van de te bewijzen conclusie. Als we bij het zoeken naar bewijzen zo’n restrictie kunnen aannemen, is het zoeken veel sneller te verrichten. Zulke bewijzen heten ‘cut‐free’ (zonder snede), de stap p → q, q → r ⇒ p → r waarin propositieletter q links wel staat maar rechts niet kunnen we zien als het ‘wegsnijden’ van q. ◊ Vervulbaar‐ In gewone conversatie ‘bewijzen’ we zelden formeel. Het gaat er dan meer heidstaken om, consistente informatie te verstrekken. Dit ‘consistency management’ (satisfiability) heeft als logische kernvraag of een gegeven verzameling beweringen een model heeft. Dit is de zogenaamde vervulbaarheid van die verzameling, in

2


het Engels: ‘satisfiability’. Dezelfde vraag doet zich in een ander jasje voor bij ontwerpen, bijvoorbeeld het ontwerp van een digitaal circuit dat moet voldoen aan vooraf gegeven Boolese specificaties, of dat van een multi‐ actorsysteem dat moet voldoen aan vooraf gegeven kennislogische eisen. Evaluatietaken In wezen eenvoudiger dan vervulbaarheidstaken, maar ook zeer nuttig, (model checking) zijn evaluatietaken (ook wel bekend onder de naam verificatietaken). Hoe bepalen we de waarheidswaarde van een formule in een model? Dit is de controle of een gegeven structuur voldoet aan zekere eisen die we van tevoren hebben gesteld. In het Engels: ‘model checking’. Het checken van specificaties voor een gegeven proces is van deze aard, evenals het bepalen van eigenschappen van een circuit van Boolese schakelingen. VOORBEELD 7.2 Logische taken kunnen ook tezamen voorkomen in eenzelfde situatie. Zo moet in de rechtszaal de aanklager bewijzen dat de beklaagde schuldig is: een bewijstaak voor een conclusie uit de voorliggende gegevens. Maar de verdediger heeft slechts de vervulbaarheidstaak om een scenario te schetsen dat past bij die gegevens, maar waarin zijn cliënt onschuldig is. Ook evalua‐ tietaken kunnen voorkomen, namelijk bij het vaststellen van het toelaatbare bewijsmateriaal. ◊ Vergelijkings‐ Er zijn nog heel andere genres taken. Heel belangrijk zijn bijvoorbeeld ver‐ taken (model gelijkingstaken. Wanneer zijn twee Boolese circuits equivalent, of twee mo‐ comparison) dellen voor de predikaatlogica, of twee multi‐actorsystemen ‐ in die zin dat ze dezelfde formules van de relevante taal waar maken? Dit soort informa‐ tie is cruciaal bij het vereenvoudigen van voorgestelde machines of infor‐ matieprocessen. VOORBEELD 7.3 De onderstaande figuur bevat twee verschillende modellen, die toch de‐ zelfde informatie uitdrukken, namelijk dat zowel actor a als actor b niet weet of p (en dat ze dit ook van elkaar weten, enzovoort).

We kunnen dit inzien door bijvoorbeeld in de p‐situatie linksboven te be‐ ginnen, en dan met een a‐pijl naar de ¬p‐situatie rechtsboven te gaan. In de rechterfiguur kunnen we zo’n overgang simuleren door in de p‐situatie onder te beginnen, en naar de ¬p‐situatie boven te gaan met een a‐pijl. Dit kunnen we vanuit iedere situatie doen, voor a‐pijlen en b‐pijlen, waarbij we bovendien ervoor blijven zorgen dat de waarheidswaarde van p blijft cor‐ responderen: of allebei waar, of allebei onwaar. Evenzo kunnen we een stap die we eerst rechts maken links simuleren. Zo’n simulatie twee kanten

3


op heet een bisimulatie. Als dit kan, dan volgt hieruit dat iedere kennislo‐ gische formule die rechts waar is, ook links waar is, en andersom. De modellen hebben dus dezelfde informatie‐inhoud: we kunnen ze niet van elkaar onderscheiden in de taal van de kennislogica. ◊ 7.2

Hoe moeilijk zijn logische taken? Onze volgende vraag betreft de moeilijkheid van deze logische taken. Een evaluatietaak in de propositielogica, dat wil zeggen het uitrekenen van een waarheidswaarde in een waarheidstabel, lijkt op het eerste gezicht een‐ voudig, en gelukkig is dat ook inderdaad zo. Een rij in een waarheidstabel komt overeen met een propositielogische waardering. In die rij vullen we één voor één de waarheidswaarden in voor alle subformules van een gege‐ ven formule. Dit kost ons evenveel ‘tijd’ (stappen) als het aantal subformu‐ les van die formule. En het aantal subformules is weer ongeveer gelijk aan de lengte van die formule: het aantal symbolen. Men zegt wel dat deze eva‐ luatietaak in de orde van grootte is van de lengte van de formule. Evaluatie in de propositielogica kost dus zogenaamde lineaire tijd, gemeten in de lengte van de invoerformule. Daarentegen is het is veel lastiger om te bepalen of een formule een model heeft (satisfiability), omdat we nu in het ergste geval alle rijen in de waar‐ heidstabel zullen moeten nagaan. Dit is een exponentieel aantal, namelijk alle combinaties van nullen en enen voor de propositieletters in de formule. VOORBEELD 7.4 We kijken nog eens naar de waarheidstabel voor de formule p ∧ ¬q van voorbeeld 3.4 p q p ∧ ¬ q 1 1 1 0 0 1 1 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 Hierin komen twee propositieletters voor. Deze formule is vervulbaar want er is een waardering waarvoor de formule waar is, namelijk als p waar is en q onwaar. Om te bepalen of een formule waarin twee propositieletters voor‐ komen vervulbaar is, moeten we in het ergste geval vier rijen (namelijk twee tot de macht van deze twee propositieletters) van de waarheidstabel onderzoeken. Maar voor deze formule zijn we bij de tweede rij al klaar! Complexiteitsanalyses gaan altijd uit van het ergste dat ons kan overko‐ men. In de praktijk kan het meevallen.

4


Om te bepalen dat de waardering waarin p waar en q onwaar is, een model is van de formule (‘model checking’) moeten we één keer de waarde van een negatie bepalen, namelijk de negatie van q, en één keer de waarde van een conjunctie, die van p en ¬q. De lengte van een formule is het aantal symbolen waar de formule uit bestaat. De formule p ∧ ¬q bestaat uit vier symbolen, of zes, als we de haakjes van de conjunctie meetellen, als in (p ∧ ¬q). Een formule kan natuurlijk nooit meer logische connectieven hebben dan het aantal symbolen. In het ergste geval is het aantal symbolen de lengte van de formule min één, zoals in ¬¬¬¬¬¬p. Daarom kost een evaluatietaak in de propositielogica lineaire tijd. ◊ VOORBEELD 7.5 Nu willen we bepalen of de formule p1 ∧ p2 ∧ ... ∧ p99 ∧ (p100 ∧ ¬p100) vervul‐ baar is. Hierin komen 100 propositieletters voor. Als we blind gaan zoeken, 100 100 moeten we dus een waarheidstabel met 2 rijen gaan aflopen; 2 is onge‐ 30 10 veer 10 (want 2 = 1024) dus met een minuut rekentijd per rij komen we dan met gemak boven de ouderdom van het heelal uit. Niettemin ziet u meteen dat de formule onvervulbaar is, vanwege de contradictie p100 ∧ ¬p100 aan het eind. En dit ‘zien’ is ook met geringe mechanische moeite uit te voeren. Er zijn vele methoden om sneller vervulbaarheid te bepalen. Dit is zelfs een belangrijk specialisme in de informatica (Boolean satisfiability ◊ checking, SAT checking). Soortgelijke vragen rijzen bij de rijkere taal van de predikaatlogica. Hoe moeilijk is het bijvoorbeeld om voor een formule ∀x ∃y R(x, y) met twee kwantoren te bepalen of deze waar is in een gegeven model van n objecten? 2 Op het eerste gezicht is het antwoord hierop: dit duurt n stappen. In het ergste geval moeten we namelijk alle (n) objecten één voor één voor x invullen, en voor elk daarvan weer alle (n) objecten proberen als mogelijke y. In het algemeen verwachten we dus exponentiële tijd voor de evaluatie van een formule met kwantoren, als we het model en die formule als invoerparameters nemen: namelijk het aantal objecten van het model tot de macht van de grootste ‘nesting’ van kwantoren in de formule. Maar ook hier kunnen verrassingen optreden die tot lagere complexiteit leiden! Het nu volgende voorbeeld bevat zo’n verrassing. VOORBEELD 7.6 Vind de beroemdheid Dit instructieve voorbeeld is van Anne Kaldewaij. Een ‘beroemdheid’ is iemand die niemand anders kent, maar wel door ieder ander wordt gekend. Hoe bepalen we zo snel mogelijk of een groep een beroemdheid heeft, en wie dat is? Het gaat hier om de vraag of in een gegeven model de predikaatlogische formule ∃x ∀y (y ≠ x → (K(y, x) ∧ ¬K(x, y))) waar is. Omdat er een stapeling van twee kwantoren is, zou men verwachten dat dit kwadratische tijd kost. Het kan echter lineair! We geven daartoe aan iedereen een rood balletje, voor ‘potentiële beroemdheid’. Nu herhalen we de volgende procedure:

5


Zolang er nog minstens twee mensen met rode balletjes zijn, pak er dan twee, zeg x en y, en kijk of x de persoon y kent. Zo ja, neem dan x het rode balletje af, zo nee, neem y het balletje af. De unieke overblijver met een balletje wordt nu nog even getest op de eigenschap beroemdheid te zijn. Dit hele proces loopt hoogstens drie keer door het domein: namelijk twee keer om de overblijver met het rode balletje te bepalen (twee objecten kie‐ zen, net zo vaak als het aantal objecten), en één keer om voor alle anderen te testen of zij die overblijver kennen en de overblijver hen niet kent. Daar‐ mee is de complexiteit lineair. ◊ Van de complexiteit van vergelijkingstaken geven we geen concreet voor‐ beeld. We formuleren nog eens de drie besproken typische taken van een logische taal: – Model checking (verificatie/evaluatie): Gegeven een model en een formule, is de formule waar in het model? – Satisfiability (vervulbaarheid): Gegeven een formule, is er een model dat de formule waarmaakt? – Model comparison (vergelijking): Gegeven twee modellen, maken deze dezelfde formules waar? Als we de precieze rekencomplexiteit van al deze taken kennen, dan heb‐ ben we een redelijk ‘profiel’ van het computationele gedrag van zo’n lo‐ gisch systeem. We zullen alleen wat voorbeelden geven van de complexiteit van dit soort kwesties voor de logische talen van dit boek. Maar voordat we dat kunnen doen, moeten we natuurlijk wel iets preciezer zijn over wat we bedoelen met rekencomplexiteit! Dit is op zich al een belangrijk vakspecia‐ lisme in de praktische en theoretische informatica. 7.3 Computationale complexiteit Een taak is effectief opgelost als je er een algoritme voor kunt schrijven, misschien als programma in een of andere programmeertaal. Bij een JA/NEE‐vraag ‘P?’ wordt de bewering P als invoer aan een mechanische procedure gegeven die na een eindig aantal stappen steeds het juiste ant‐ woord geeft. Een voorbeeld van zo’n vraag is: kunnen we uit een begin‐ situatie een gewenste eindsituatie bereiken via een eindig aantal stappen? Heel veel taken in de informatica, zoals het bevragen van gegevensbanken, of zoektaken in de kunstmatige intelligentie, komen neer op het bepalen van dergelijke ‘bereikbaarheid’ van een doel uit een beginpunt. VOORBEELD 7.7 Graph reachability (bereikbaarheid in een graaf) Gegeven is een eindige gerichte graaf G en twee knopen s (‘beginknoop’) en t (‘eindknoop’). Is er een pad van s naar t? Deze vraag is te beantwoorden met het volgende algoritme:

6


R wordt de verzameling rode knopen. Kleur om te beginnen alleen s rood. B wordt de verzameling blauwe knopen. Deze is in eerste instantie leeg. Herhaal nu de volgende procedure: pak een rode knoop uit R, verf deze blauw (voeg deze aan B toe), en vervang die knoop in R door al zijn (direc‐ te) opvolgers in de graaf, ‘tenzij je ze al gehad hebt’, dat wil zeggen: tenzij ze al rood of blauw zijn. Met andere woorden: verf alle niet gekleurde op‐ volgers rood. Als er niet zulke opvolgers zijn, dan krimpt R dus. Stop als R leeg is. Als t nu blauw is, dan is t bereikbaar uit s, en anders niet. Dit algoritme is correct en eindigt in kwadratische tijd ten opzichte van het aantal knopen van de graaf. Dit kunnen we als volgt inzien. Stel n is het aantal knopen in de graaf. Ten hoogste iedere knoop verkleurt een keer van rood naar blauw, ieder van die knopen heeft ten hoogste alle andere kno‐ pen als opvolger, en aan het eind moeten we nog even de verzameling B doorlopen, die ten hoogste alle knopen bevat. In totaal zijn dit hooguit n(n – 1) + n stappen. Omdat voor grote n de lineaire factoren verwaarloos‐ baar zijn ten opzichte van kwadraten, en n en n – 1 dan bijna hetzelfde zijn, 2 ◊ zeggen we: de orde van grootte is n . De kunst van efficiënt programmeren loopt via dergelijke slimme represen‐ taties met lage complexiteit. Vergelijk dit ook met voorbeeld 7.6 van ‘vind de beroemdheid’. Graden van groei Als een antwoord op een JA/NEE‐vraag ‘P?’ altijd in eindig veel stappen puur mechanisch bepaald kan worden noemen we het probleem beslisbaar. Het is dan immers te ‘beslissen’ (uit te maken) of het antwoord op deze vraag JA dan wel NEE is. De complexiteit van zo’n beslisbare procedure is een functie van de lengte van de invoer van die procedure (zoals bij een propositielogische formule: het aantal symbolen). Daarbij speelt het aantal rekenstappen een belangrijke rol. Dit wordt de tijdscomplexiteit van het probleem genoemd. We hebben al gezien dat het aantal rekenstappen lineair kan zijn in de invoer, en ook dat het een groter polynoom kan zijn dan lineair, bijvoor‐ beeld kwadratisch, zoals in voorbeeld 7.7. Beide noemen we van polyno‐ miale complexiteit. Als de rekencomplexiteit polynomiaal is ten opzichte van de invoer noemen we een probleem in de klasse P (waarbij P inderdaad voor polynomiaal staat). Als x de invoerlengte is, dan is bijvoorbeeld ax + b 3 lineair en ax derdegraads, en beide zijn polynomen, dus deze problemen zitten allebei in P. Als de rekencomplexiteit daarentegen exponentieel is als functie van de invoerlengte vinden we het ‘heel complex’. Deze klasse x noemen we Exptime: deze exponentiële tijd ziet er ten minste uit als a . Oudere lezers herinneren zich nog de groeigrafieken van de ‘Club van Rome’ in de zeventiger jaren, die aangaven hoe vervuiling en andere doemscenario’s op deze akelig snelle manier toenamen. En het kan zelfs x nog erger dan Exptime, zoals bijvoorbeeld in x! en in 2 2 . Er zitten ook nog complexiteitsklassen tussen polynomiaal en exponentieel, maar daar gaan we niet op in.

7


VOORBEELD 7.8 Graph reachability, GR, is in P, omdat voor een gegeven graaf G de proce‐

dure altijd eindigt na hooguit een aantal stappen van een kwadratische orde van grootte (namelijk n(n – 1) + n). ◊ Een logische analogie kan helpen deze begrippen nog iets beter te begrij‐ pen. Hiervoor zagen we al dat propositielogische evaluatie in P zit. Testen op propositielogische vervulbaarheid leek exponentiële complexiteit te heb‐ ben maar zit in feite in een lagere complexiteitsklasse, tussen P en Exptime in. Zelfs als een taak in P zit, blijft een algoritme van lineaire tijd prettiger dan één van kwadratische tijd, enzovoorts: een polynoom van lagere graad is altijd weer beter dan een van hogere graad. De kunst van het program‐ meren bestaat doorgaans uit het geschikt kiezen van datastructuren en instructies, om zo laag mogelijk in rekencomplexiteit uit te komen. Problemen in P gelden als doenlijk (in het Engels: ‘tractable’) en alles daar‐ buiten als ondoenlijk (‘intractable’), hetgeen overigens niemand verhindert allerlei speciale gevallen toch op de computer op te lossen. Onbeslisbaarheid Het kan dus, zoals we al zagen, nog veel erger qua complexiteit. En som‐ mige problemen zijn helemaal niet met een algoritmische methode op te lossen: deze heten onbeslisbaar. Wie zou niet graag willen kunnen vermijden dat zijn computer vastloopt? Dit is het Stopprobleem: ‘Bepaal bij een wille‐ keurig programma en willekeurige invoer, of het programma voor die invoer termineert.’ In het Engels is het probleem bekend als het ‘Halting problem’. Het is nu een feit dat dit Stopprobleem onbeslisbaar is. Dit feit werd bewe‐ zen door Alan Turing in 1936. Er zijn dus geen wondermiddelen die auto‐ matisch ongewenst gedrag van onze computers detecteren. Nog zo’n onbe‐ slisbare vraag is bijvoorbeeld die naar de equivalentie van twee gegeven programma’s, bijvoorbeeld in een eenvoudige imperatieve programmeer‐ taal: geven ze op alle invoer dezelfde waarden? De oudste voorbeelden van onbeslisbare problemen komen uit de logica. VOORBEELD 7.9 Predikaatlogica is onbeslisbaar In de propositielogica hebben we een beslissingsprocedure om te bepalen of een gegeven formule een tautologie is, of niet: maak de waarheidstabel, loop alle waarderingen langs en bepaal de waarde van de hele formule voor die waardering, en als er overal énen staan, is het een tautologie. Maar in de predikaatlogica bestaat zo’n procedure niet. (We laten details achter‐ wege.) Het resultaat dat de predikaatlogica onbeslisbaar is danken we aan Alonzo Church, die hiertoe gebruik maakte van de beroemde Stelling van Gödel. Hoe zit het dan met bijvoorbeeld onze kennislogica, die qua kracht in lag tussen de propositielogica en de predikaatlogica? Deze blijkt weer beslisbaar, maar wel met een wezenlijk complexer algoritme dan voor de propositielogica. ◊

8


De algemene moraal is deze: niet elk eenvoudig formuleerbaar probleem inzake redeneren, rekenen of informatieverwerking heeft een mechanische oplossing! Ook hier merken we weer op dat de praktijk toch enig optimis‐ me wettigt. Zelfs onbeslisbare problemen kunnen systematisch worden aangepakt. Er zijn namelijk allerlei bewijsmethodes voor de predikaat‐ logica, waarmee we ‘meestal’ wel uit de voeten kunnen. In dit verband maken we nog een opmerking. Onze voorbeelden in dit hoofdstuk geven slechts bovengrenzen: hoeveel tijd‐ of ruimtestappen hebben we hoogstens nodig, in het ergste geval? Om een probleem precies te plaatsen in de complexiteitshiërarchie moeten we ook een ondergrens geven: hoeveel stappen kan de oplossing minstens vergen, wat is de mini‐ male complexiteit? Maar in het algemeen wordt het gedrag van een algo‐ ritme in de praktijk bepaald door rekentijd op willekeurige invoer, zodat we eerder zouden moeten spreken over een gemiddelde complexiteit. Deze verdere kwesties laten we hier terzijde. Tegen deze achtergrond eindigen we met een meer theoretische kwestie. Hoe moeilijk is het vervulbaarheids‐ of geldigheidsprobleem van de propo‐ sitielogica nu werkelijk? Moet het exponentieel, of wordt er wellicht toch nog een slim algoritme gevonden dat het in polynomiale tijd afkan? Deze vraag staat bekend als het ‘P = NP’ probleem, dat voorkomt op de lijst van ‘Tien Meest Beroemde Open Vragen van de Wiskunde’, in 2000 gepubli‐ ceerd door het Cray Institute. Het is opmerkelijk dat een zo eenvoudig lo‐ gisch systeem als de propositielogica, in wezen al bekend sinds de Klassie‐ ke Oudheid, nog zulke nieuwe vragen weet op te werpen.

9


Samenvatting Een probleem is beslisbaar als een antwoord op een JA/NEE‐vraag ‘P?’ altijd in eindig veel stappen puur mechanisch bepaald kan worden. De complexi‐ teit van zo’n beslissingsprocedure is een functie van de lengte van de in‐ voer van die procedure. Daarbij speelt het aantal rekenstappen (tijdscom‐ plexiteit) een rol. Wat betreft het aantal rekenstappen is lineair minder complex dan (vanaf tweedegraads) polynomiaal, en polynomiaal minder complex dan exponentieel. Al deze genres complexiteit komen voor in de propositielogica, en overigens ook in de kennislogica van hoofdstuk 6. Sommige belangrijke problemen zijn zelfs onbeslisbaar, dat wil zeggen dat geen enkel programmeerbaar algoritme, hoe ingewikkeld ook, ze kan oplossen. Bijvoorbeeld, het is onbeslisbaar of bij een willekeurig program‐ ma en willekeurige invoer, het programma voor die invoer termineert. Dit staat bekend als het Stopprobleem. Maar ook logische geldigheid in syste‐ men als de predikaatlogica is van deze hoge complexiteit. Dit document bevat hoofdstuk 7 van de cursus Logica in actie. De volledige cursus is beschikbaar op http://www.spinoza.ou.nl. © Open Universiteit Nederland; Uitgeverij: Sdu Uitgevers, ’s‐Gravenhage. Dit materiaal is gelicentieerd onder een Creative Commons Licentie. Zie de licentie voor details. The content on this site is licensed under a Creative Commons Licentie. See licence for more details.

10


OPGAVE 7.1

OPGAVE 7.2

Opgaven Voer het ‘graph reachability’ algoritme van voorbeeld 7.7 uit voor de volgende graaf. Als beginknoop s neemt u knoop 1 in de figuur. Als eindknoop t neemt u knoop 4.

Voer het ‘vind de bekendheid’ algoritme van voorbeeld 7.6 uit voor de volgende graaf.

11


7.1

7.2

Uitwerkingen van de opgaven bij hoofdstuk 7 We voeren het ‘graph reachability’ algoritme van voorbeeld 7.7 uit voor de gegeven graaf, met s als beginknoop en t als eindknoop. R is de verzamelingen rode knopen, B is de verzameling blauwe knopen. Om te beginnen is R = {1} en B = ∅. De handeling waarbij we een rode knoop uit R selecteren, blauw maken, en zijn opvolgers rood, noemen we een stap. Merk op dat de selectie van een rode knoop in een stap non‐ deterministisch (onbepaald) is. We kiezen dus gewoon een rode knoop ‐ niet per se de eerste als we de elementen van de verzamelingen R van links naar rechts lezen. Het is mogelijk dat u in uw antwoord een andere keuze gemaakt heeft, maar dat uw antwoord toch goed is. R = {1} B = ∅ Kies 1, de opvolgers zijn 2, 3 en 7. R = {2, 3, 7} B = {1} Kies 2, de opvolgers zijn 1, 3, en 4; 4 heeft geen kleur. R = {3, 4, 7} B = {1, 2} Kies 3, de opvolgers zijn 2, 4, 5, en 6; 5 en 6 hebben geen kleur. R = {4, 5, 6, 7} B = {1, 2, 3} Kies 6, alle knopen zijn inmiddels gekleurd. R = {4, 5, 7} B = {1, 2, 3, 6} Kies 4. R = {5, 7} B = {1, 2, 3, 4, 6} Kies 7. R = {5} B = {1, 2, 3, 4, 6, 7} Kies 5. R = ∅ B = {1, 2, 3, 4, 5, 6, 7} De knoop t = 4 maakt deel uit van de verzameling B. Dus t is vanuit s be‐ reikbaar. Merk op dat we het algoritme niet stoppen op het moment dat 4 in de verzameling B komt, maar dat het algoritme volgens afspraak pas termineert als de verzameling R leeg is. We voeren het ‘vind de bekendheid’ algoritme van voorbeeld 7.6 uit voor de gegeven graaf. De verzameling punten (of mensen) met rode balletjes is R. De keuze voor twee uit R is non‐deterministisch (net als in de vorige opgave). We geven de keuze aan in het overzicht hierna ‐ u heeft wellicht een andere keuze gemaakt! R = {1, 2, 3, 4} Kies 2 en 4, 2 kent 4 niet, neem dus 4 rood af. R = {1, 2, 3}

12


Kies 1 en 3, 1 kent 3, neem dus 1 rood af. R = {2, 3} ‘Kies’ 2 en 3, 2 kent 3, neem dus 2 rood af. R = {3} We moeten nu testen of de unieke overblijver (er is altijd een unieke overblijver!) een beroemdheid is. Dit is zo, want (1, 3), (2, 3), (4, 3) zitten alledrie in K, maar (3, 3) zit niet in K.

13

Complexiteit van berekeningen

Recommend Documents