Separating the complexity classes NL and NP

2000/04/17 by David B. Benson, Benson, David B.
Computer Science · #Computational Complexity (cs.CC) #F.1.3 #F.4.1 #FOS: Computer and information sciences #cs.CC

paper · pdf · doi:10.48550/arxiv.cs/0004009

Withdrawn

arxiv created 2000/05/12 · arxiv updated 2009/11/30

Abstract

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

Related

• A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions
• A Solution to the P versus NP Problem
• NP is not AL and P is not NC is not NL is not L
• We must know -- We shall know
• P is a proper subset of NP