The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 7204396 (Why is no real title available?)
- A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
- Handbook of graph theory
- Knapsack problems for NL
- Languages that Capture Complexity Classes
- Logspace optimization problems and their approximability properties
- Lower bounds based on the exponential time hypothesis
- Monotone monadic SNP and constraint satisfaction
- New problems complete for nondeterministic log space
- Nondeterministic Space is Closed under Complementation
- On the Structure of Polynomial Time Reducibility
- On the complexity of k-SAT
- Optimization, approximation, and complexity classes
- Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)
- Space-bounded reducibility among combinatorial problems
- Supportive oracles for parameterized polynomial-time sub-linear-space computations in relation to L, NL, and P
- The complexity of theorem-proving procedures
- The method of forced enumeration for nondeterministic automata
- Undirected connectivity in log-space
- Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems
- Which problems have strongly exponential complexity?
Cited in
(4)- Logical expressibility of syntactic NL for complementarity and maximization
- Power of counting by nonuniform families of polynomial-size finite automata
- 2-cnfs and logical embeddings
- Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters
This page was built for publication: The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6098146)
