ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY

DOI10.17223/20710410/47/8zbMath1455.68071OpenAlexW3011555672MaRDI QIDQ5151438

Alexander N. Rybalov

Publication date: 17 February 2021

Published in: Prikladnaya Diskretnaya Matematika (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/pdm697

zbMATH Keywords

NP-completenessBoolean circuitBoolean satisfiability problemgeneric complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topics in the theory of algorithms (68W01) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (1)

Heuristic algorithms for recognition of some cubic hypersurfaces

Cites Work

• Unnamed Item
• Generic case completeness
• Average case completeness
• Generic-case complexity, decision problems in group theory, and random walks.
• Average Case Complete Problems
• ON GENERIC NP-COMPLETENESS OF THE BOOLEAN SATISFIABILITY PROBLEM

This page was built for publication: ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY