Computer Science – Computational Complexity
Scientific paper
2006-06-13
Computer Science
Computational Complexity
19 pages, 4 figures
Scientific paper
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.
Chapdelaine Philippe
Grandjean Etienne
No associations
LandOfFree
Lower bounds and complete problems in nondeterministic linear time and sublinear space complexity classes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Lower bounds and complete problems in nondeterministic linear time and sublinear space complexity classes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower bounds and complete problems in nondeterministic linear time and sublinear space complexity classes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-45931