3 citations · 5 across the 6 of their papers we have counts for
7 papers
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…
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…
The complexity of propositional proofs
Grigoriy V. Bokov
In this paper, we consider the complexity of propositional proofs of classical and intuitionistic tautologies. In fact, we describe a nondeterministic polynomial-time decision proc…
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…
On the number of variables in undecidable superintuitionistic propositional calculi
Grigoriy V. Bokov
In this paper, we construct an undecidable 3-variable superintuitionistic propositional calculus, i.e., a finitely axiomatizable extension of the intuitionistic propositional calcu…
Undecidable problems for propositional calculi with implication
Grigoriy V. Bokov
In this article, we deal with propositional calculi over a signature containing the classical implication with the rules of modus ponens and substitution. For these calculi w…
Undecidability of the problem of recognizing axiomatizations for implicative propositional calculi
Grigoriy V. Bokov
In this paper we consider propositional calculi, which are finitely axiomatizable extensions of intuitionistic implicational propositional calculus together with the rules of modus…