scientific article; zbMATH DE number 7204396
DOI10.4230/LIPICS.MFCS.2017.62zbMATH Open1441.68102arXiv1709.10453MaRDI QIDQ5111278FDOQ5111278
Publication date: 26 May 2020
Full work available at URL: https://arxiv.org/abs/1709.10453
Title of this publication is not available (Why is that?)
Recommendations
- State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis
- State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis
- Time-space tradeoffs for satisfiability
- On Linear CNF Formulas
linear-space hypothesisNL optimizationNL searchshort reductionsub-linear spaceBoolean formula satisfiability problemsyntactic NL
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07)
Cites Work
- Title not available (Why is that?)
- Which problems have strongly exponential complexity?
- Relationships between nondeterministic and deterministic tape complexities
- Undirected connectivity in log-space
- Title not available (Why is that?)
- The complexity of theorem-proving procedures
- On the complexity of \(k\)-SAT
- The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
- Nondeterministic Space is Closed under Complementation
- Title not available (Why is that?)
- The method of forced enumeration for nondeterministic automata
- New problems complete for nondeterministic log space
- Handbook of graph theory
- Logspace optimization problems and their approximability properties
- On tape-bounded complexity classes and multihead finite automata
- Space-bounded reducibility among combinatorial problems
- Knapsack problems for NL
- Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems
Cited In (5)
- Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice
- 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
- The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
- 2-cnfs and logical embeddings
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111278)
