2006/06/13 by Philippe Chapdelaine, Chapdelaine, Philippe, Étienne Grandjean +1
Computer Science · #Advanced Graph Theory Research #Coding theory and cryptography #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.1.3 #F.4.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)
paper · pdf · doi:10.48550/arxiv.cs/0606058
openalex publication_date 2006/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Proving lower bounds remains the most difficult of tasks in computational complexity theory. In this paper, we show that whereas most natural NP-complete problems belong to NLIN (linear time on nondeterministic RAMs), some of them, typically the planar versions of many NP-complete problems are recognized by nondeterministic RAMs in linear time and sublinear space. The main results of this paper are the following: as the second author did for NLIN, we give exact logical characterizations of nondeterministic polynomial time-space complexity classes; we derive from them a class of problems, which are complete in these classes, and as a consequence of such a precise result and of some recent separation theorems using diagonalization, prove time-space lower bounds for these problems.