资源描述：
《Complexity Classifications for复杂度分类》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ComplexityClassificationsforPropositionalAbductioninPost’sFramework∗NadiaCreignou1,JohannesSchmidt1,MichaelThomas21LIF,UMRCNRS6166,Aix-MarseilleUniversit´e163,AvenuedeLuminy,13288MarseilleCedex9,Francecreignou@lif.univ-mrs.frjohannes.schmidt@lif.univ-mrs.fr2Institutf¨urTheoretischeInformat
2、ik,GottfriedWilhelmLeibnizUniversit¨atAppelstr.4,30167Hannover,Germanythomas@thi.uni-hannover.deAbstract.Inthispaperweinvestigatethecomplexityofabduction,afundamentalandimportantformofnon-monotonicreasoning.Givenaknowledgebaseexplainingtheworld’sbehavioritaimsatfindinganexplanationforsomeo
3、bservedmanifestation.Inthispaperweconsiderpropositionalabduction,wheretheknowledgebaseandthemanifesta-tionarerepresentedbypropositionalformulae.TheproblemofdecidingpwhetherthereexistsanexplanationhasbeenshowntobeΣ2-completeingeneral.Wefocusonformulaeinwhichtheallowedconnectivesaretakenfro
4、mcertainsetsofBooleanfunctions.Weconsiderdifferentvari-antsoftheabductionprobleminrestrictingboththemanifestationsandthehypotheses.Forallthesevariantsweobtainacomplexityclassifica-tionforallpossiblesetsofBooleanfunctions.Inthisway,weidentifyeasiercases,namelyNP-complete,coNP-completeandpoly
5、nomialcases.Thus,wegetadetailedpictureofthecomplexityofthepropositionalabductionproblem,hencehighlightingsourcesofintractability.Further,weaddresstheproblemofcountingtheexplanationsanddrawacom-pletepictureforthecountingcomplexity.Keywords:abduction,computationalcomplexity,Post’slattice,pr
6、opo-sitionallogic,booleanconnectivearXiv:1006.4923v1[cs.CC]25Jun2010∗SupportedbyANRAlgorithmsandcomplexity07-BLAN-0327-04andDFGgrantVO630/6-1.AnearlierversionappearedintheProc.of12thInternationalConferenceonthePrinciplesofKnowledgeRepresentationandReasoning,KR’2010,Toronto,Canada.1Introdu
7、ctionThispaperisdedicatedtothecomputationalcomplexityofabduction,afunda-mentalandimportantformofnon-monotonicreasoning.Givenacertainconsis-tentknowledgeabouttheworld,abductivereasoningisusedtogenerateexplana-tions(oratleasttellingifthereisone)forobservedmanifestatio
