On the complexity of unique circuit SAT

DOI10.1007/s10958-020-04813-1zbMath1442.68053OpenAlexW3025319872MaRDI QIDQ2202678

A. A. Lialina

Publication date: 29 September 2020

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10958-020-04813-1

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Networks and circuits as models of computation; circuit complexity (68Q06) Computational aspects of satisfiability (68R07)

Cites Work

• Unnamed Item
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• NP is as easy as detecting unique solutions
• New worst-case upper bounds for SAT
• New methods for 3-SAT decision and worst-case analysis
• An improved exponential-time algorithm for k -SAT
• Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework
• Algorithms – ESA 2005

This page was built for publication: On the complexity of unique circuit SAT