Graph Isomorphism is PSPACE-complete

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Combining 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.

Keywords

Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/137009

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0708.4075
 http://arxiv.org/abs/0708.4075

Collections

arXiv