ON GENERIC COMPLEXITY OF THE VALIDITY PROBLEM FOR BOOLEAN FORMULAS

DOI10.17223/20710410/32/9zbMath1490.68114OpenAlexW2471110028MaRDI QIDQ5150742

Alexander N. Rybalov

Publication date: 15 February 2021

Published in: Prikladnaya diskretnaya matematika (Search for Journal in Brave)

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

zbMATH Keywords

generic complexityvalidity problem for Boolean formulas

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)

Related Items (4)

ON GENERIC NP-COMPLETENESS OF THE BOOLEAN SATISFIABILITY PROBLEM ⋮ ON GENERIC COMPLEXITY OF THE GRAPH CLUSTERING PROBLEM ⋮ ON GENERIC COMPLEXITY OF THE EXISTENTIAL THEORIES ⋮ The generic complexity of the graph triangulation problem

Cites Work

• Unnamed Item
• Unnamed Item
• Average-case complexity and decision problems in group theory.
• Generic complexity of Presburger arithmetic
• Generic-case complexity, decision problems in group theory, and random walks.
• The halting problem is decidable on a set of asymptotic probability one
• Generic complexity of undecidable problems
• The complexity of theorem-proving procedures

This page was built for publication: ON GENERIC COMPLEXITY OF THE VALIDITY PROBLEM FOR BOOLEAN FORMULAS