The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
From MaRDI portal
Publication:6098146
DOI10.1016/j.jcss.2023.03.001OpenAlexW2760351616WikidataQ123111275 ScholiaQ123111275MaRDI QIDQ6098146
Publication date: 12 June 2023
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8134/
short reductionparameterized decision problemlinear space hypothesissub-linear-space computabilitysyntactic NL2CNF Boolean formula satisfiability
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Knapsack problems for NL
- The method of forced enumeration for nondeterministic automata
- Optimization, approximation, and complexity classes
- Space-bounded reducibility among combinatorial problems
- Which problems have strongly exponential complexity?
- Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)
- Supportive oracles for parameterized polynomial-time sub-linear-space computations in relation to L, NL, and P
- Logspace optimization problems and their approximability properties
- Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems
- Handbook of Graph Theory
- Undirected connectivity in log-space
- Languages that Capture Complexity Classes
- Nondeterministic Space is Closed under Complementation
- On the Structure of Polynomial Time Reducibility
- New problems complete for nondeterministic log space
- A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
- Monotone monadic SNP and constraint satisfaction
- The complexity of theorem-proving procedures
- State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis
- On the complexity of \(k\)-SAT
