2026-07-23T04:54:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8134 2024-03-06T10:40:57Z ddc:004 open_access

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis Yamakami, Tomoyuki sub-linear space linear space hypothesis short reduction Boolean formula satisfiability problem NL search NL optimization Syntactic NL We aim at investigating the solvability/insolvability of nondeterministic logarithmic-space (NL) decision, search, and optimization problems parameterized by size parameters using simultaneously polynomial time and sub-linear space on multi-tape deterministic Turing machines. We are particularly focused on a special NL-complete problem, 2SAT - the 2CNF Boolean formula satisfiability problem-parameterized 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_3-a restricted variant of 2SAT in which each variable of a given 2CNF formula appears as literals in at most 3 clauses-cannot be solved simultaneously in polynomial time using strictly "sub-linear" (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 logarithmic-space reductions may no longer preserve polynomial-time sub-linear-space 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tomoyuki Yamakami 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.62 urn:nbn:de:0030-drops-81344 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.62 eng https://creativecommons.org/licenses/by/3.0/legalcode