Complexity of some problems concerning varieties a

COMPLEXITYOFSOMEPROBLEMSCONCERNINGVARIETIESANDQUASI-VARIETIESOFALGEBRAS∗CLIFFORDBERGMAN†ANDGIORASLUTZKI‡SIAMJ.COMPUT.c2000SocietyforIndustrialandAppliedMathematicsVol.30,No.2,pp.359–382Abstract.Inthispaperweconsiderthecomplexityofseveralproblemsinvolvingfinitealgebraicstructures.GivenfinitealgebrasAandB,theseproblemsaskthefollowing.(1)DoAandBsatisfypreciselythesameidentities?(2)Dotheysatisfythesamequasi-identities?(3)DoAandBhavethesamesetoftermoperations?Inadditiontothegeneralcaseinwhichweallowarbitrary(finite)algebras,weconsidereachoftheseproblemsundertherestrictionsthatalloperationsareunaryandthatAandBhavecardinalitytwo.Webrieflydiscusstherelationshipoftheseproblemstoalgebraicspecificationtheory.Keywords.variety,quasi-variety,clone,term-equivalence,computationalcomplexity,logarith-micspace,polynomialspace,hyperexponentialtime,nondeterminismAMSsubjectclassifications.Primary,68Q25;Secondary,08B15,08C15,08A40,68Q65PII.S00975397983459441.Introduction.Thereareseveralrelationshipsbetweenmathematicalstruc-turesthatmightbeconsidered“fundamental.”Firstandforemostiscertainlytheisomorphismrelation.Questionsaboutisomorphicstructuresoccurthroughoutmath-ematicsandapplytouniversalalgebras,topologicalspaces,graphs,partiallyorderedsets,etc.Manyotherrelationshipsaremorespecialized.Forexample,giventwographsGandH,onemaywishtoknowwhetherHisasubgraphofGorperhapsaminorofG.Properlyformulated,questionsabouttheserelationshipsgiverisetocomplexityquestions.Generallyspeaking,wemustimposesomesortoffinitenessassumptiononthestructuresinquestionsothatnotionsofcomputationalcomplexitymakesense.Thecomplexityofvariousisomorphismproblemshasreceivedagreatdealofattention.Thegraphisomorphismproblemhasbeenintensivelystudied,partlybecauseitsexactrelationshiptotheclassesPandNPisstillunknown,andpartlybecauseitprovidesaparadigmforotherproblemsofunknowncomplexitystatus.Inthiscase,bothgraphsareassumedtohavefinitelymanyverticesandfinitelymanyedges.Withasimilarformulation,theisomorphismproblemforalgebrashasthesamecomplexityasdoesgraphisomorphism.Moregenerally,Kozen[17]showedthattheisomorphismproblemforfinitelypresentedalgebrashasthissamecomplexity.See[4,16,19]forfurtherdiscussionandreferencesontheisomorphismproblem.Inthispaperweconsiderthecomplexityofthreerelationshipsthatarisefromconsiderationsinuniversalalgebra.Anyalgebraicstructuresatisfiescertainidentitiesandfailstosatisfyothers.Roughlyspeaking,anidentityisanequalitybetweentwoexpressionsbuiltfromtheoperationsofthealgebra.Examplesofidentitiesaretheassociativelaw(whichinvolvesonebinaryoperation)andDeMorgan’slaw(twobinary∗ReceivedbytheeditorsOctober19,1998;acceptedforpublication(inrevisedform)October26,1999;publishedelectronicallyJune3,2000.ApreliminaryversionofthispaperappearedinThe16thSymposiumonTheoreticalComputerScience(STACS’99),LectureNotesinComput.Sci.1563,Springer-Verlag,Berlin,1999,pp.163–172.†DepartmentofMathematics,IowaStateUniversity,400CarverHall,Ames,IA50011-5454([e-mail]).‡DepartmentofComputerScience,IowaStateUniversity,226AtanasoffHall,Ames,IA50011-5454([e-mail]).359360CLIFFORDBERGMANANDGIORASLUTZKIoperationsandoneunaryoperation).Identitiesareoneoftheprimaryorganizingtoolsinalgebra.GiventwoalgebrasAandB,wemayaskwhethertheysatisfypreciselythesamesetofidentities.Noticethatthisisafarweakernotionthanisomorphism.Forexample,anyalgebrasatisfiesthesameidentitiesaseachofitsdirectpowers.Nevertheless,ifAandBsatisfythesameidentities,thentheywillbeconstrainedtobehaveinasimilarway.Oneofourproblems,calledVar-Equiv,isthis:Giventwofinitealgebrasofthesamefinitesimilaritytype,determinewhethertheysatisfythesameidentities.Thisproblemhasimplicationsforseveralareasofcomputerscience.Formalalgebraicspecificationsareexpressionsinalanguagewhichdescribethepropertiesandinput-outputbehaviorthatasoftwaresystemmustexhibit,withoutputtinganyrestrictionsonthewayinwhichthesepropertiesareimplemented.Thisabstractionmakesformalspecificationsextremelyusefulintheprocessofdevelopingsoftwaresystemswhereitservesasareferencepointforusers,implementers,testers,andwritersofinstructionmanuals.Formalspecificationshavebeenappliedsuccessfullyindeploymentofsophisticatedsoftwaresystems;see[33],especiallythereferencesthere.Mathematically,formalalgebraicspecificationsarefirmlygroundedonalgebraicconcepts,especiallyideas,notions,andmethodsfromuniversalalgebra[6].Therelationshipbetweenimplementationandequationalspecificationcorresponds,inal-gebraicterms,totherelationshipbetweenanalgebraandasetofidentitiessatisfiedbythealgebra.Thus,twoalgebrasthatsatisfythesameidentitiescorrespondtoapairofimplementationswithpreciselythesamespecifications.Thecomputationalcomplexityoftheseproblems,intheuniversalalgebraicframework,isthusquiterel-evanttothebodyofresearchinformalspecificationtheory,andtotheconstructionofsupportingtoolssuchastheoremproversandmodelcheckers.Generalizingthenotionofidentity,wearriveataquasi-identity.Weshallleaveaprecisedefinitionforsection2,butcrudelyspeaking,aquasi-identityinvolvesaconj