On complexity of restricted fragments of Decision DNNF

Dit artikel onderzoekt de complexiteit van beperkte fragmenten van Decision DNNF, met name $\wedge_d$-OBDD en gestructureerde Decision DNNF, door nieuwe methoden voor ondergrenzen te ontwikkelen, exponentiële scheidingen aan te tonen en een efficiëntere variant voor CNF-formules met begrenste incidentie-treewidth te introduceren.

De kern

Stel je voor dat je een enorme, ingewikkelde puzzel hebt: een logische vergelijking met duizenden variabelen (zoals "als het regent én ik een paraplu heb, dan blijf ik droog"). In de wereld van computers en kunstmatige intelligentie noemen we dit een CNF (Conjunctive Normal Form). Het probleem is dat deze puzzels soms zo groot zijn dat ze onmogelijk op te lossen zijn voor een computer, tenzij je ze eerst herschrijft in een vorm die makkelijker te begrijpen is.

Deze paper gaat over een specifieke manier om die puzzels te herschrijven, genaamd Decision DNNF. Maar de auteurs kijken niet naar de algemene versie, maar naar een speciale, strengere variant die ze $\land^d$-OBDD noemen.

Hier is de uitleg in gewone taal, met een paar creatieve vergelijkingen:

1. De Basis: De Logische Puzzel

Stel je voor dat je een gigantische map hebt met instructies.

• De "Primal" manier: Je kijkt naar de puzzel als een geheel. Als de puzzel een bepaalde structuur heeft (zoals een boom of een netwerk met weinig verbindingen), kun je hem heel compact maken. Dit is als het oplossen van een sudoku waarbij je de regels goed begrijpt; het gaat snel.
• De "Incidence" manier: Hier kijken we naar de puzzel alsof we elke regel apart bekijken. De auteurs ontdekten dat voor deze specifieke manier van kijken, de meeste bestaande methoden vastlopen. Het is alsof je een ingewikkeld labyrint probeert te doorlopen, maar elke keer dat je een keuze maakt, moet je alles opnieuw berekenen.

2. Het Probleem: De "Stijve" Regel

De auteurs kijken naar een model genaamd $\land^d$-OBDD.

• De Analogie: Stel je voor dat je een computerprogramma schrijft dat een beslissing moet nemen. Een normaal programma (een FBDD) mag op elk moment vragen: "Is het regenen?" of "Heb ik een paraplu?". Het kan de volgorde van vragen aanpassen aan de situatie.
• De $\land^d$-OBDD: Dit is een stijver programma. Het moet vragen stellen in een vaste volgorde. Eerst altijd "Regen?", dan altijd "Paraplu?", dan altijd "Schoenen?". Het mag niet van plan veranderen.
• De ontdekking: De auteurs bewijzen dat als je deze strikte volgorde moet aanhouden, het programma voor bepaalde soorten puzzels (die "incidence treewidth" hebben) explosief groot wordt. Het is alsof je probeert een heel groot huis te bouwen met alleen rechte lijnen, terwijl het huis bolle muren heeft. Je moet eindeloos veel extra bakstenen toevoegen om de bocht te maken.

3. De "Fooling Set": De Valstrik

Hoe bewijzen ze dit? Ze gebruiken een truc die ze een "fooling set" (valstrik-set) noemen.

• De Metafoor: Stel je voor dat je een leraar bent die een examen afneemt. Je wilt weten of de student echt begrijpt wat er gebeurt, of dat hij alleen maar raden doet.
• De auteurs maken een lijst met honderden verschillende situaties (de "fooling set"). Ze bewijzen dat voor elke unieke situatie, de computer een unieke plek in zijn geheugen moet hebben om die situatie te onthouden. Als je 1.000 verschillende situaties hebt, moet je 1.000 verschillende plekken in je geheugen hebben.
• Ze tonen aan dat voor deze specifieke puzzels, het aantal unieke situaties zo groot is dat het geheugen van de computer (de grootte van het model) exponentieel groeit. Het wordt onbeheersbaar groot.

4. De "Apply" Operatie: Het Koppelen van Puzzels

Een ander belangrijk onderdeel van de paper gaat over het koppelen van twee modellen (de Apply operatie).

• De Situatie: Stel je hebt twee kleine, handzame instructieboeken (Model A en Model B). Je wilt ze samenvoegen tot één groot boek (A EN B).
• Het Probleem: Bij een normaal OBDD is dit makkelijk: je plakt de boeken gewoon aan elkaar. Maar bij het $\land^d$-OBDD kan dit leiden tot een explosie. Het nieuwe boek wordt niet twee keer zo groot, maar misschien wel een miljard keer zo groot.
• De Oplossing (De "Irregularity Index"): De auteurs vinden een manier om dit te meten. Ze noemen het de "Irregularity Index" (onregelmatigheids-index).
  • Vergelijking: Stel je voor dat je twee treinen moet koppelen. Als de rails perfect recht zijn (lage index), kun je ze makkelijk koppelen. Maar als de rails kronkelen en niet op elkaar aansluiten (hoge index), moet je een enorme, ingewikkelde constructie bouwen om ze te verbinden.
  • Ze bewijzen dat als de "onregelmatigheid" laag is, het koppelen nog steeds snel en efficiënt gaat. Als de onregelmatigheid hoog is, is het een ramp.

5. De Nieuwe Held: "Structured $\land^d$-FBDD"

Tot slot introduceren ze een nieuwe, iets minder strenge versie van het model, genaamd Structured $\land^d$-FBDD.

• De Metafoor: Stel je voor dat de oude, strenge regels (Structured Decision DNNF) zeggen: "Je mag alleen rechte lijnen trekken." De nieuwe versie zegt: "Je mag rechte lijnen trekken, maar je mag ook een paar bochten maken, zolang je maar niet te ver afwijkt van het plan."
• Het Resultaat: Deze nieuwe versie is veel krachtiger. Het kan bepaalde soorten puzzels die de oude versie niet aankon, toch compact houden. Het is alsof je een flexibele slang hebt in plaats van een stijve pijp; hij past zich beter aan de vorm van de puzzel aan.

Conclusie: Wat betekent dit voor de toekomst?

De auteurs zeggen eigenlijk:

1. Pas op met stijve regels: Als je een computerprogramma dwingt om vragen in een vaste volgorde te stellen, kan het voor bepaalde complexe problemen onmogelijk groot worden.
2. Flexibiliteit is goud: Als je een beetje flexibiliteit toelaat (zoals in hun nieuwe "Structured" model), kun je veel grotere en complexere problemen oplossen zonder dat het systeem instort.
3. Nieuwe vragen: Ze sluiten af met een lijst van vragen die nog onbeantwoord zijn. Ze hopen dat hun nieuwe concepten (zoals de "onregelmatigheids-index") andere wetenschappers zullen helpen om nog betere manieren te vinden om deze logische puzzels op te lossen.

Kortom: Ze hebben een nieuwe manier bedacht om te meten hoe "stijf" een computerprogramma is, en bewezen dat te veel stijfheid leidt tot een enorme, onbeheersbare grootte. Maar met een beetje meer flexibiliteit (en de juiste meetlat), kunnen we die problemen toch nog oplossen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "On complexity of restricted fragments of Decision DNNF" van Andrea Calì en Igor Razgon, geschreven in het Nederlands.

Titel: Over de complexiteit van beperkte fragmenten van Decision DNNF

Auteurs: Andrea Calì (Universiteit van Napels "Federico II") en Igor Razgon (Durham University).

---

1. Probleemstelling en Context

Het artikel richt zich op Decision DNNF (Decomposable Negation Normal Form), ook wel bekend als $\land^d$-fbdd. Dit is een belangrijk model voor kenniscompilatie (knowledge compilation) dat gebruikt wordt om Booleaanse functies, specifiek CNF-formules (Conjunctive Normal Form), compact weer te geven.

• Achtergrond: DNNF's zijn krachtiger dan traditionele circuits omdat ze decomposeerbare AND-gates ($\land^d$) gebruiken. Een bekend resultaat is dat CNF's met een beperkte primal treewidth (de structuur van de variabelen in de clausules) een FPT (Fixed-Parameter Tractable) representatie toelaten in DNNF.
• Het Open Vraagstuk: De complexiteit van het vertalen van CNF's met een beperkte incidence treewidth (de structuur van het verband tussen variabelen en clausules) naar Decision DNNF is lang een open vraag geweest.
  • Open Question 1: Bestaat er een functie $f$ en een constante $a$ zodat een CNF met incidence treewidth $k$ kan worden weergegeven als een Decision DNNF van grootte $f(k) \cdot n^a$?
• De Uitdaging: Decision DNNF kan worden gezien als een Free Binary Decision Diagram (FBDD) met toegevoegde $\land^d$-knooppunten. Het probleem is dat de $\lor$-knooppunten (beslissingen) alleen de waarde van variabelen kunnen "gissen", maar het is onduidelijk hoe ze de vervulling van clausules efficiënt kunnen hanteren zonder de structuur te verliezen.

2. Methodologie

De auteurs benaderen het probleem door de Decision DNNF te beperken tot twee specifieke subklassen om inzicht te krijgen in de onderliggende complexiteit:

1. $\land^d$-OBDD: Een Decision DNNF die voldoet aan een vaste lineaire volgorde van variabelen (vergelijkbaar met een OBDD, maar met $\land^d$-knooppunten).
2. Structured Decision DNNF: Een model waarbij de $\land^d$-knooppunten een vaste "vtree" (variabele boom) respecteren.

Nieuwe Methodologische Instrumenten:

• Fooling Sets voor $\land^d$-OBDD: De auteurs introduceren een generieke methode om ondergrenzen te bewijzen. Ze definiëren een "fooling set" van toewijzingen (assignments) en een bijbehorende "unbreakable set" van variabelen. Als een grote fooling set bestaat, moet de grootte van de $\land^d$-OBDD exponentieel groot zijn.
• Embeddability en Irregularity Index: Voor het bestuderen van de Apply-operatie (conjunction) introduceren ze het concept van embeddability in een lineaire volgorde. Ze definiëren een irregularity index ($k$) die meet hoe ver een $\land^d$-OBDD afwijkt van een standaard OBDD. Dit stelt hen in staat om te analyseren wanneer de Apply-operatie efficiënt is.
• Structured $\land^d$-fbdd: Ze definiëren een nieuwe, minder restrictieve versie van "structuredness" die specifiek is ontworpen voor $\land^d$-fbdd, waarbij alleen de expliciete $\land^d$-knooppunten een vtree moeten respecteren, niet de beslissingsknooppunten.

3. Belangrijkste Resultaten

A. Ondergrenzen en Scheidingen voor $\land^d$-OBDD

• XP-ondergrens: De auteurs bevestigen en bewijzen opnieuw met hun nieuwe methode dat het vertalen van CNF's met beperkte incidence treewidth naar $\land^d$-OBDD een XP-grootte vereist (exponentieel in de parameter $k$). Dit betekent dat een statische volgorde van variabelen onvoldoende is om de complexiteit van incidence treewidth te beheersen.
• Exponentiële Scheidingen:
  • Er bestaat een klasse van CNF's die polynomiëel groot is als FBDD, maar exponentieel groot moet zijn als $\land^d$-OBDD.
  • Er bestaat een klasse van CNF's die polynomiëel groot is als $\land^d$-OBDD, maar exponentieel groot moet zijn als OBDD.
  • Significantie: Dit toont aan dat het toevoegen van $\land^d$-knooppunten aan een OBDD (onder statische volgorde) een enorme krachtswinst biedt vergeleken met een gewone OBDD, maar dat deze kracht niet voldoende is voor bepaalde structuren (zoals roosters) die wel goed passen bij FBDD.

B. Complexiteit van de Apply-operatie

• Exponentiële Explosie: In het algemeen leidt de Apply-operatie (het nemen van de conjunctie van twee $\land^d$-OBDD's) tot een exponentiële toename in grootte, zelfs als beide modellen dezelfde variabelevolgorde respecteren.
• Efficiëntie onder Beperkingen: De auteurs identificeren een speciaal geval waar Apply efficiënt is. Als twee modellen embeddable zijn in dezelfde lineaire volgorde en een lage irregularity index hebben, dan kan hun conjunctie worden weergegeven als een $\land^d$-OBDD met grootte $(|B_1| \times |B_2|)^{O(k_1+k_2)}$.
  • Dit biedt een nieuwe theoretische richting voor het efficiënt combineren van kenniscompilatiemodellen.

C. Structured $\land^d$-fbdd

• De auteurs introduceren Structured $\land^d$-fbdd. In tegenstelling tot de strikte "Structured Decision DNNF", is dit model krachtiger.
• Resultaat: Dit model heeft een FPT-representatie voor CNF's die kunnen worden omgezet in een CNF met beperkte primal treewidth door het verwijderen van een constante aantal clausules.
  • Vergelijking: Voor zowel $\land^d$-OBDD als de oorspronkelijke Structured Decision DNNF wordt al een XP-ondergrens geactiveerd door slechts twee lange clausules. Het nieuwe model is dus aanzienlijk robuuster.
• De vraag of Structured $\land^d$-fbdd een FPT-representatie toelaat voor alle CNF's met beperkte incidence treewidth, blijft open.

4. Significatie en Conclusie

• Beperking van Statieke Ordening: De resultaten tonen aan dat als Decision DNNF een FPT-representatie toelaat voor CNF's met beperkte incidence treewidth, deze representatie niet gebaseerd kan zijn op een statische volgorde van variabelen. Dynamische ordening is essentieel voor efficiëntie in dit domein.
• Componentanalyse: De resultaten suggereren dat bij het gebruik van statische ordening (zoals in veel SAT-solvers), de tijd die wordt besteed aan componentanalyse (het opdelen van het probleem in onafhankelijke delen) cruciaal is voor de efficiëntie.
• Nieuwe Concepten: De introductie van de irregularity index en embeddability biedt nieuwe hulpmiddelen om de relatie tussen verschillende kenniscompilatiemodellen (DNNF, OBDD, FBDD) te kwantificeren en te vertalen.
• Open Vragen: Het artikel sluit af met een lijst van open vragen, waaronder:
  • Kan de ondergrens voor Structured $\land^d$-fbdd worden bewezen voor incidence treewidth?
  • Bestaat er een vergelijkbare ondergrens voor "oblivious regular resolution" (een bewijssysteem) geparametriseerd door incidence treewidth?
  • Kan de "irregularity index" worden gebruikt om de efficiëntie van de Apply-operatie voor bredere klassen van modellen te definiëren?

Samenvattend: Dit artikel levert een diepgaande analyse van de beperkingen en mogelijkheden van Decision DNNF-varianten. Het bewijst dat statische ordening onvoldoende is voor bepaalde complexe structuren, introduceert nieuwe methoden voor het bewijzen van ondergrenzen, en biedt een veelbelovend nieuw model (Structured $\land^d$-fbdd) dat potentieel de brug slaat tussen primal en incidence treewidth complexiteit.