搜索
SomeDichotomyTheoremsonConstant-freeQuanti edBooleanFormulasV ctorDalmau DepartamentLSI,UniversitatPolit ecnicadeCatalunya,CampusNord,M odulC5,JordiGironaSalgado,1-3,Barcelona08034,Spain,dalmau@lsi.upc.es10September199712PagesplusanappendixwithproofsAbstractInthispaperwestudythesatis abilityofconstant-freequanti- edbooleanformulas.Weconsiderthefollowingclassesofquanti edbooleanformulas.Fixa nitesetofbasicbooleanlogicalfunctions.Takeconjunctionsofthesebasicfunctionsappliedtovariablesinar-bitraryway.Finally,quantifyexistentiallyoruniversallysomeofthevariables.Schaefer[20]earlierstudiedthesatis abilityofquanti edbooleanformulaswithconstants.HeshowedthateverysuchproblemiseitherinPorPSPACE-completeandhegaveacompleteclassi cationofthetractablecases.WeextendthePSPACE-hardnessresultstoconstant-freequanti edbooleanformulasobtainingadichotomytheoremforthesatis abilityofconstant-freequanti edbooleanformulas.We ndthat,infact,constantsdonotmakeadi erencewhenconsideringthesatis abilityofquanti edbooleanformulas.Wealsoproveadichotomytheoremthatallowsustoimproveapreviousresultonthelearnabilityofquanti edbooleanformulasgettingridoftheconstants. WorksupportedinpartbytheSpanishGovernmentthroughgrantAP9443716784andtheDGICYT(projectKOALABP95-0797)andtheECthroughtheEspritBRAProgram(WorkingGroup8556,NeuroColtandproject20244,ALCOMIT).11IntroductionTheproblemofdeterminingwhetheragivenpropositionalformulaissat-is ablehasbeenwidelystudied.ItiswellknownthatevenrestrictedtoformulasinconjunctivenormalformwithatmostthreeliteralsperclausetheproblemisNP-complete[5].Therefore,researchershaveattemptedtodeterminethesatis abilityofsubclassesofpropositionalbooleanformu-las,inparticularinsideCNF.Forexample,thesatis abilityinpolynomialtimeofbijunctiveformulaswasshownin[5]andcanbedonealsoinlineartime[17].Thesatis abilityofHornformulasandread-twiceCNFformulashavealsobeenshowntobedecidableinlineartime[9,18].Schaefer[20]proposedalargesetofclassesofbooleanformulasandstudiedtheirassociatedsatis abilityproblem,calledtheGeneralizedSatis- abilityProblem.Heprovedaveryremarkableresult:Foreverysuchclassofformulas,itssatis abilityiseitherinPorNP-complete.Thisdichotomyissomewhatsurprisingsinceonemightexpectthatanysuchlargeanddiverseclassofproblemswouldincludesomerepresentativeofthemanyintermedi-atedegreesofcomplexitywhichpresumablyliebetweenthesetwoextremes.Furthermore,hegaveacompleteclassi cationofthepolynomial-timede-cidableclasses.Wenowprovidetheinformalde nitionstostateSchaefer’sclassi cationresultforthesatis abilityproblem.Precisede nitionsoftheconceptsin-volvedwillbegiveninSection2.LetS=fR1;:::;Rmgbea nitesetoflogicalrelations.De neaFormula(S)tobeanybooleanformulaformedbyconjunctionsofanynumberofclausesoftheformRi(x1;:::;xk),wherex1;:::;xkarepossiblyrepeatedvariablesandkistherankofRi.Anexample:Considerthesetofbooleanformulasformedbyaconjunc-tionofclauseswithatmostthreeliteralsperclause.EverysuchformulacanbeexpressedasaformulainFormula(S)withthesetoflogicalrelationsS=fR0;R1;R2;R3g,de nedby:R0(x;y;z) x_y_z;R1(x;y;z) x_y_z;R2(x;y;z) x_y_z;R3(x;y;z) x_y_z:Schaefershowedthatthesatis abilityofFormula(S)ispolynomial-timedecidableifandonlyifatleastoneofthefollowingconditionholds: EveryrelationinSissatis edwhenallvariablesare0. EveryrelationinSissatis edwhenallvariablesare1.2 EveryrelationinSisde nablebyaCNFformulainwhicheachclausehasatmost2literals. EveryrelationinSisde nablebyaCNFformulainwhicheachclausehasatmostonenegatedvariable. EveryrelationinSisde nablebyaCNFformulainwhicheachclausehasatmostoneunnegatedvariable. EveryrelationinSisthesetofsolutionsofasystemoflinearequationsoverthetwo-element eldf0;1g.Weareinterestedinthesatis abilityofquanti edbooleanformulas.ItiswellknownthatthisproblemisPSPACE-complete[21,22]andsomee orthasbeendevotedtoclassifythepolynomial-timedecidableclasses.Alineartimealgorithmwhenallclauseshaveatmosttwovariablescanbefoundin[3].In[13]acubictimealgorithmforquanti edHornformulashasbeenshowed.Wede nean98-Formula(S)tobethesetofquanti edbooleanformulasthatweobtainifwetakeaformulainFormula(S)andwequantifyexisten-tiallyoruniversallyinanyordersomeofthevariables.WecalltheformulasconstructedinthiswayGeneralizedquanti edbooleanformulas.Ifweallowtoputconstantsf0;1gintheplaceofvariablesthenwehavealargersetofformulasdenotedby98-FormulaC(S).Schaefer[20]showedadichotomytheoremforquanti edbooleanfor-mulaswithconstants.Moreprecisely,heprovedthatthesatis abilityof98-FormulaC(S)(withconstants)ispolynomialtimedecidableifandonlyifatleastoneofthefollowingconditionsholds: EveryrelationinSisde nablebyaCNFformulainwhicheachclausehasatmost2literals. EveryrelationinSisde nablebyaCNFformulainwhicheachclausehasatmostonenegatedvariable. EveryrelationinSisde nablebyaCNFformulainwhicheachclausehasatmostoneunnegatedvariable. EveryrelationinSisthesetofsolutionsofasystemoflinearequationsoverthetwo-element eldf0;1g.Theuseofformulaswithconstantsinsteadofthemostnaturalconstant-freeformulasisatechnicaltrickthatisbeenusedasanintermediatestepin3thequanti er-freecasebecauseit