On Closure Properties of #P in the Context of PF f

OnClosurePropertiesof#PintheContextofPF#PMitsunoriOgiharayDept.ComputerScienceUniv.ofRochester([e-mail])ThomasThieraufFakultatfurInformatikUniverstatUlm([e-mail])SeinosukeTodaDept.ComputerScienceUniv.Electro-Communications([e-mail])OsamuWatanabeDept.ComputerScienceTokyoInstituteofTechnology([e-mail])AbstractForanyoperatoroninteger-valuedfunctions,wesaythat#PisclosedunderincontextPF#Pif,foreveryf2#P,[f]belongstoPF#P.Forseveraloperators,itisshownthattheclosurepropertiesof#PunderintheabovesenseiscloselyrelatedtotherelationshipsbetweenP#P[1]andhigherclassessuchasPHPPandPPPP.1.IntroductionCountingisoneofthekeynotionsincomputation.Recently,variouscountingproblemshavereceivedconsiderableattention(see,e.g.,[Sch90])and,inordertomodelthem,therehavebeenintroducedandextensivelystudiedcomplexityclassescalledcountingclasses,typiedbyfunc-tionclasses#P[Val79],spanP[KST89],andGapP[FFK94],andlanguageclassesPP[Gil77],P[PZ83],C=P[Sim75,Wag86a],andthecountinghierarchyCH[Tor91,Wag86b].Unfortu-nately,manyofthequestionsregardingcountingclasses,eventheonesaboutinclusionrelation,areleftopen.Confrontedwithsuchdicultiesinresolvingproblemsabsolutely,researchershaveApartoftheworkwasdonewhiletherstauthorwasvisitingDepartmentofComputerScience,StateUni-versityofNewYorkatBualo,andthesecond,third,andfourthauthorswerevisitingDepartmentofComputerScience,UniversityofRochester.ThisresearchissupportedinpartbyJSPS/NSFInternationalCollaborationGrantJSPS-ENGR-207/NSF-INT-9116781.TherstauthorissupportedinpartbyNSFGrantgrantCCR-9002292.ThesecondauthorissupportedinpartbyDFGPostdoctorialScholarshipTh472/1-1andNSFgrantCCR-8957604.yPreviouslyknownasMitsunoriOgiwara.1devisedtoolstoobtainrelativeanswersthatpromoteabetterunderstandingoftheoriginalque-stions.(Cf.EventhoughtheP=?NPquestionisopen,throughvariousresearch,nowwehaveampleknowledgeabouthowNPwouldbedierentfromPiftheyweredierent.)Thepurposeofthispaperistointroduceastructuralconceptthathelpsustodeepenourunderstandingonrelationshipsbetweencountingclasses.Thecentralcountingclassis#P,theclassoffunctionsthatcountthenumberofsolutionstoNPdecisionproblems.Theclass#Pisknowntocontainmanynaturalfunctions,suchasthepermanentofintegermatrices,whichisoneoftherstnontrivialfunctionsproventobein#Pand,infact,proventobe#P-complete[Val79].Withtheincreaseinthenumberofinterestingexamples,thepropertiesof#P,especially,theclosurepropertiesof#P,hasbecomeacentralresearchtopic.Intuitively,wesaythat#Pisclosedunderanoperationifthefunctionsconstructedbyapplyingto#Pfunctionsalwaysbelongto#P.Forinstance,forany#Pfunctionsf(x)andg(x),thefunctionsf(x)+g(x)andf(x)g(x)alsobelongto#P,Herewesaythat#Pisclosedunderadditionandmultiplicationandthatbothadditionandmultiplicationareclosurepropertiesof#P.Closurepropertiesof#Phaveplayedimportantroles,bothexplicitlyandimplicitly,inthestudyofcountingclassesoflanguages[BHW91,BRS91,CH90,FR91],andmanyclosurepropertiespossessedby#Phavebeenfound(See[OH93]).Nevertheless,theclassdoesnotseemtopossessclosurepropertiesundersomeprimitiveoperations,suchasmodiedsubtraction.1OgiwaraandHemachandra[OH93]haveestablishedthetheoryforclosurepropertiesoffunctionclasses.Theyhaveclariedwhy#Pseemstolacksuchprimitiveclosureproperties.Theyshowedthat#PisclosedundermodiedsubtractionifandonlyifthecountinghierarchycollapsestoUP,whichisthesmallestcountingclass.Informallyput,wecannothopethatmodiedsubtractionof#Pfunctionsisdoneby#Punlessallthedecisionproblemsinthecountinghierarchy,includingthosebelongingtothepolynomial-timehierarchy,aresolvedbyNPmachinesthathaveatmostoneacceptingpathperinput.Althoughitisnotlikelythat#Pfunctionscancomputemodiedsubtractionof#P-functions,wenoticethatsubtractionisalmostcomputedby#Pfunctions.Letf(x)andg(x)betwo#Pfunctionsandp(n)beapolynomialsuchthatmaxff(x);g(x)g2p(jxj)forallx.Thenitiseasytodesigna#Pfunctionh(x)suchthatforallx,h(x)=2p(jxj)+(f(x)g(x)).Clearly,therstbitofh(x)representsthesignoff(x)g(x)andthelastp(jxj)bitsofh(x)representf(x)g(x).So,wecaneasilyretrievef(x)g(x)fromh(x).Herewemaysaythatthefunctionh(x)realizesthesubtractionoff(x)andg(x),astheactualvalueofthesubtractionisencodedinthebinaryrepresentationofh(x),andwemightaswellsaythat#Pisclosedundersubtractioninsomeweakersense,asweonlyhavetodosomesimplepost-computationonthe1Themodiedsubtractionofmfromn,denotedbynm,ismaxfnm;0g.Since#Pfunctionsarealwaysnonnegative,#Pisprovablynotclosedundertheusualsubtraction.2outcomeofa#Pfunction.Thisobservationisgeneralizedtothefollowingdenitionofclosurepropertiesof#PincontextPF#P.Denition1.1.Foranyoperator(or,functor),let[#P]denotetheclassoffunctionsob-tainedbyapplyingtosomefunctionin#P,andletPF#P=fhf:h2PF;f2#Pg,wherehfdenotestheordinarycompositionofthetwofunctionsandPFdenotestheclassofallpolynomial-timecomputablefunctions.Wesaythat#PisclosedunderincontextPF#Pif[#P]PF#P.Inotherwords,isaclosurepropertyof#PincontextPF#Pifthefunctiongeneratedbyap-plyingto#Pcanbecomputedby#Pwithsupplementarypolynomial-ti