Lower bounds and complete problems in nondeterministic linear time and sublinear space complexity classes
| dc.creator | Chapdelaine, Philippe | |
| dc.creator | Grandjean, Etienne | |
| dc.date | 2006-06-13 | |
| dc.date.accessioned | 2026-07-07T07:13:04Z | |
| dc.date.available | 2026-07-07T07:13:04Z | |
| dc.description | 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. | |
| dc.description | 19 pages, 4 figures | |
| dc.identifier | https://arxiv.org/abs/cs/0606058 | |
| dc.identifier | http://arxiv.org/abs/cs/0606058 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/112307 | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic in Computer Science | |
| dc.subject | F.1.3; F.4.1 | |
| dc.title | Lower bounds and complete problems in nondeterministic linear time and sublinear space complexity classes | |
| dc.type | text |