Satisfiability in Boolean Logic (SAT problem) is polynomial?

DOI10.17516/1997-1397-2021-14-5-667-671OpenAlexW4205154944MaRDI QIDQ5071401

Vladimir Vladimirovich Rybakov

Publication date: 21 April 2022

Published in: Journal of Siberian Federal University. Mathematics & Physics (Search for Journal in Brave)

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

zbMATH Keywords

satisfiability problemBoolean logicSAT algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Unnamed Item
• Unnamed Item
• Logical equations and admissible rules of inference with parameters in modal provability logics
• Problems of substitution and admissibility in the modal system Grz and in intuitionistic propositional calculus
• A criterion for admissibility of rules in the modal system S4 and intuitionistic logic
• Admissible rules for pretable modal logics
• Admissibility of logical inference rules
• Logical cryptanalysis as a SAT problem: Encoding and analysis of the U. S. Data Encryption Standard
• Generating hard satisfiability problems
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures

This page was built for publication: Satisfiability in Boolean Logic (SAT problem) is polynomial?