t a t u

CaptureComplexitybyPartition

YijiaChen⋆1andEnshaoShen⋆⋆2

1Universit´edeParis-Sud,LaboratoiredeRechercheenInformatique,Bˆatiment490,

F-91405OrsayCedex,France,

@

2ShanghaiJiaoTongUniversity,DepartmentofComputerScience,

Shanghai200030,China,

shen-es@

inthispaperaspecialextendedlogic,partition

logicbadonsocalledpartitionquantifiers,isabletocapturesome

importantcomplexityclassNP,PandNLbyitsnaturalfragments.

TheFagin’sTheoremandImmerman-Vardi’sTheoremarerephrad

edual

operatorsforthepartitionquantifiersareintroducedtoexposomeof

iculartheyenableus

toshowa0-1lawforthepartitionlogic,evenwhenfinitevariableinfini-

quence,partitionlogiccannotcount

eringitsbettertheoreti-

calpropertiesandtoolsthanthoofcondorderlogic,partitionlogic

mayprovideuswithanalternative,yetuniforminsightfordescriptive

complexity.

1Introduction

Fromfinitemodeltheory,ormoreprecily,thetheoryofdescriptivecomplexity,

weknowthatallimportantcomplexityclasshavetheirownnaturallogic

rwords,foreachofthecomplexityclass,thereexistsa

logicallanguagecapablefordefiningexactlythoproblemffectivelycheckable

firstofsuchcorrespondenceisduetoFagin[4],which

equatesnondeterministicpolynomialtimewithexistentialcondorderlogicΣ1

1

.

Someofthemajorresultsaresummarizedbythefollowingtable:

ComplexityClass

NP

P

NL

⋆supportedbyCalife,aprojectof“R´eauNationaldeRechercheen

T´el´ecommunications”.

⋆⋆supportedinpartbyNationalFoundationofNaturalScienceofChina.

issues,culminatinginImmerman’sfamousproofofNL=co-NL[10].Never-

thelesscomparedwiththeTuringMachine,theunifiedmachinemodelbehind

complexityclass,tance,we

havedifferentwaystoreachthemfromfirstorderlogic:byaddinghigherorder

quantifiers(orderlogic)orrecursiveoperators(fixed-point

andtransitiveclosurelogic),andthelatterenjoysaninductiveflavorexplicitly.

Someefforthasalreadybeenmadetounifythelogictheories,oneisbyGr¨adel[6],

heidentifiedsomefragmentsofcondorderlogic,saycondorderHornand

Kromlogics,pproachistoaugment

thefirstorderlogicbyariesofLindstr¨omquantifierswhicharebadonsome

particularcompleteproblems[1],suchasusingHamiltonianPathOperatorsto

captureNP[18].

PartitionLogicarisfromtheubiquitousmathematicaloperationas:parti-

tionatintoveraldisjointunion,overeachpartitionsubtcertainproperty

issatisfiicalexampleisthecongruentrelation.H.-D.

Ebbinghausfirstin1990’sintroducedthePartitionQuantifierstomimicsuch

eamaygofurtherbacktoMaltiz,yetwithsome

extrainfinitecardinalityconstraint[13],whichiswellbeyondfinitemodeltheory.

Asitcandefinetheconnectivityofgraphandsomeothernon-first-orderprop-

erties,ritpossssome

nicemodel-theoreticpropertieswhicharenotsharedbycondorderlogic,such

asthedownwardL¨owenheim-Skolen-TarskitheoremandtheTarskiChainthe-

orem[16].Inthemeantimepartitionquantifierscanbelookedasaspecialkind

ofmonotoneLindstr¨omones,sotheirEhrenfeucht-Fraiss´egameismoreelegant

andtractablethanthatofcondorderlogic[15].Thereforeinan,partition

logicislocatesinthelowerlevel(nearfirstorderlogic)ofthefragment-spectrum

ofcondorderlogic.

Theattempttoapplypartitionlogicincomputersciencestartedata-

riesofpapers[14,15,17],inwhichitwasprovedthatonwordandtreestruc-

tures,monadicfragmentofpartitionlogiciquivalenttomonadiccondorder

foundanaturalfragmentofpartitionlogic

equivalenttotransitiveclosurelogic,whileImhofshowedanothersublogicof

itcorrespondstoboundedfixedpointlogic[8].Allthefactsdemonstratethat

paper,weshowthatpartitionlogicmayrveasauniformplatformtoaccom-

modatethemostimportantpartofcomplexityspectrum,,PandNL.

OurmaintheoremprovidesaunifiedcharacterizationofNPandPinpartition

logiconfiniteorderedstructures,inwhichsomekeyparametersofthemachine

ixplicitlyrelatedtothoofthepartitionquantifier,therebygivingtheTuring

machineaclearerlogicalreflilewewillalsoprovea0-1lawfor

partitionlogic,thuswithoutordering,itevencannotdefinesomeverysimple

countingproblemlikeParityoverarbitraryfinitestructures.

Thepaperisorganizedasfollows:wegivethedefinitionofpartitionlogicin

Section2,n3reviewsitsrelationwith

transitiveclosurelogicandleastfixedpointlogicbymeansofthedualoperators

ofpartitionquantifiers,whilethecapturingofNPandPbypartitionlogicis

n5isdevotedtoits0-1law.

Weassumethereaderhassomebasicknowledgeoffinitemodeltheory,espe-

ciallythoresultscompiledintheprecedingtable,comprehensivedetailsand

referencescanbefoundin[3,11].

2Preliminary

Inthispaper,onlyfiotherwi

declared,structuresarenotnecessarilyfi

uFO,SOtodenotefi(ψ)is

thetoffreevariablesinψofacertainlogic.|A|isthecardinalityofthet

A,alsoweoverload|a.

ThelanguageofpartitionlogicistheenlargementofFObyanewformation

rule:foranyk,m,n>0,ifϕ(

y)isawell-formedformulawith|

y|=nk,thenkP

m,n

y

ϕ(

y)isalsowell-formed,andinwhichyarebound.

DefistructureAandz|,A|=kP

m,n

y

ϕ(y,e]where

FV(ϕ)⊆{y,

a

0

...b

0

...e]forarbitrarya

m−1

∈Uand

b

n−1

∈V.

ObviouslypartitionlogicisafragmentofSOandalsoamonotoneLindstr¨om

venience,wewillwritePm,n

y

ϕinlieuof1P

m,n

y

ϕ,andthequantifiers

areparticularlynamedmonadicpartitionquantifiers[17].Foranyk,m,n>0,

letFO(kPm,n)betheextensionofFOwithkPm,eviate

FO(ωP1,1)=