scientific article; zbMATH DE number 7204396

DOI10.4230/LIPICS.MFCS.2017.62MaRDI QIDQ5111278zbMATH OpenFDO

Authors Tomoyuki Yamakami

Publication date 26 May 2020

Full work available at URL https://arxiv.org/abs/1709.10453

zbMATH Keywords

Boolean formula satisfiability problemlinear-space hypothesisNL optimizationNL searchshort reductionsub-linear spacesyntactic NL

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Time-space tradeoffs for satisfiability
• On Linear CNF Formulas

Cites work

• Handbook of graph theory
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• Knapsack problems for NL
• Logspace optimization problems and their approximability properties
• Lower bounds based on the exponential time hypothesis
• New problems complete for nondeterministic log space
• Nondeterministic Space is Closed under Complementation
• On tape-bounded complexity classes and multihead finite automata
• On the complexity of k-SAT
• Relationships between nondeterministic and deterministic tape complexities
• Space-bounded reducibility among combinatorial problems
• The complexity of theorem-proving procedures
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• 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

(3)

• 2-cnfs and logical embeddings
• The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
• Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata

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)