Separating the complexity classes NL and NP

Authors

Benson, David B.

Description

Withdrawn since -order- was overlooked. First order reductions without order are much too weak to separate.
Withdrawn

Keywords

Computational Complexity, F.1.3; F.4.1

URI

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

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0004009
http://arxiv.org/abs/cs/0004009

Collections