scientific article; zbMATH DE number 7204396
From MaRDI portal
Publication:5111278
DOI10.4230/LIPIcs.MFCS.2017.62zbMath1441.68102arXiv1709.10453MaRDI QIDQ5111278
Publication date: 26 May 2020
Full work available at URL: https://arxiv.org/abs/1709.10453
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
linear-space hypothesisNL optimizationNL searchshort reductionsub-linear spaceBoolean formula satisfiability problemsyntactic NL
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational aspects of satisfiability (68R07)
Related Items (4)
The 2CNF Boolean formula satisfiability problem and the linear space hypothesis ⋮ Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata ⋮ State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Knapsack problems for NL
- The method of forced enumeration for nondeterministic automata
- On tape-bounded complexity classes and multihead finite automata
- Space-bounded reducibility among combinatorial problems
- Which problems have strongly exponential complexity?
- The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
- Relationships between nondeterministic and deterministic tape complexities
- 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
- Nondeterministic Space is Closed under Complementation
- New problems complete for nondeterministic log space
- The complexity of theorem-proving procedures
- On the complexity of \(k\)-SAT
This page was built for publication:
