Abstract
We aim at investigating the solvability/insolvability of nondeterministic logarithmicspace (NL) decision, search, and optimization problems parameterized by size parameters using simultaneously polynomial time and sublinear space on multitape deterministic Turing machines. We are particularly focused on a special NLcomplete problem, 2SAT  the 2CNF Boolean formula satisfiability problemparameterized by the number of Boolean variables. It is shown that 2SAT with n variables and m clauses can be solved simultaneously polynomial time and (n/2^{c sqrt{log(n)}}) polylog(m+n) space for an absolute constant c>0. This fact inspires us to propose a new, practical working hypothesis, called the linear space hypothesis (LSH), which states that 2SAT_3a restricted variant of 2SAT in which each variable of a given 2CNF formula appears as literals in at most 3 clausescannot be solved simultaneously in polynomial time using strictly "sublinear" (i.e., n^{epsilon} polylog(n) for a certain constant epsilon in (0,1)) space. An immediate consequence of this working hypothesis is L neq NL. Moreover, we use our hypothesis as a plausible basis to lead to the insolvability of various NL search problems as well as the nonapproximability of NL optimization problems.
For our investigation, since standard logarithmicspace reductions may no longer preserve polynomialtime sublinearspace complexity, we need to introduce a new, practical notion of "short reduction." It turns out that overline{2SAT}_3 is complete for a restricted version of NL, called Syntactic NL or simply SNL, under such short reductions. This fact supports the legitimacy of our working hypothesis.
BibTeX  Entry
@InProceedings{yamakami:LIPIcs:2017:8134,
author = {Tomoyuki Yamakami},
title = {{The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {62:162:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8134},
URN = {urn:nbn:de:0030drops81344},
doi = {10.4230/LIPIcs.MFCS.2017.62},
annote = {Keywords: sublinear space, linear space hypothesis, short reduction, Boolean formula satisfiability problem, NL search, NL optimization, Syntactic NL}
}
Keywords: 

sublinear space, linear space hypothesis, short reduction, Boolean formula satisfiability problem, NL search, NL optimization, Syntactic NL 
Seminar: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) 
Issue Date: 

2017 
Date of publication: 

22.11.2017 