3 papers
cs.DS2018
Quantified boolean formula problem
Grigoriy V. Bokov
This paper is devoted to the complexity of the quantified boolean formula problem. We describe a simple deterministic algorithm that, for a given quantified boolean formula , st…
cs.CC2018
Complexity of the CNF-satisfiability problem
Grigoriy V. Bokov
This paper is devoted to the complexity of the Boolean satisfiability problem. We consider a version of this problem, where the Boolean formula is specified in the conjunctive norm…
math.LO2015
Undecidable iterative propositional calculus
Grigoriy V. Bokov
In this paper, we consider iterative propositional calculi, which are finite sets of propositional formulas together with the rules of modus ponens and weak substitution (when form…