Logical expressibility of syntactic NL for complementarity and maximization

DOI10.1007/978-3-031-62687-6_17MaRDI QIDQ7034640zbMATH OpenFDO

Authors Tomoyuki Yamakami

Publication date 31 January 2025

Full work available at URL https://doi.org/10.1007/978-3-031-62687-6_17

zbMATH Keywords

2SATDSTCONlinear space hypothesisMAX-CUTNLoptimization problemsecond-order logicSNLUK

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Cites work

• A compendium of problems complete for symmetric logarithmic space
• A taxonomy of problems with fast parallel algorithms
• Encyclopedia of algorithms. In 3 volumes
• scientific article; zbMATH DE number 7768354 (Why is no real title available?)
• Logspace optimization problems and their approximability properties
• Monotone monadic SNP and constraint satisfaction
• New problems complete for nondeterministic log space
• Nondeterministic Space is Closed under Complementation
• 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
• 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
• The complexity of theorem-proving procedures
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• 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?

This page was built for publication: Logical expressibility of syntactic NL for complementarity and maximization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7034640)