Graph Isomorphism is PSPACE-complete

Simple item page
dc.creatorDelacorte, Matthew
dc.date2007-08-30
dc.date.accessioned2026-07-07T08:26:38Z
dc.date.available2026-07-07T08:26:38Z
dc.descriptionCombining the the results of A.R. Meyer and L.J. Stockmeyer "The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space", and K.S. Booth "Isomorphism testing for graphs, semigroups, and finite automata are polynomiamlly equivalent problems" shows that graph isomorphism is PSPACE-complete.
dc.identifierhttps://arxiv.org/abs/0708.4075
dc.identifierhttp://arxiv.org/abs/0708.4075
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/137009
dc.subjectComputational Complexity
dc.titleGraph Isomorphism is PSPACE-complete
dc.typetext

Files

Collections

arXiv