scientific article; zbMATH DE number 7204396
DOI10.4230/LIPICS.MFCS.2017.62zbMATH Open1441.68102arXiv1709.10453MaRDI QIDQ5111278FDOQ5111278
Authors: Tomoyuki Yamakami 
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
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
- Lower bounds based on the exponential time hypothesis
- 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 (3)
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)
