Beviser for kvantificerede booleske formler
DepQBF er en søgningsbaseret beviser for kvantificerede booleske formler
(QBF) i prenex konjunktiv normalform. Den er baseret på DPLL-algoritmen
til QBF, kaldet QDPLL, med konflikt-drevne klausul og løsningsdrevet
terninglæring. Ved at analysere den syntaktiske struktur af en formel,
forsøger DepQBF at identificere uafhængige variabler. I almindelighed
kan information på uafhængige variable være repræsenteret i de formelle
rammer for afhængighedsordninger. DepQBF beregner den såkaldte
»standardafhængighedsordning« hos en given formel. Udover andre fordele
øger information på uafhængige variabler ofte friheden til
beslutningstagning og klausul læring.