Several calculi for quantified Boolean formulas (QBFs) exist, but relations between them are
not yet fully understood. This paper defines a novel calculus, which is resolution-based and …

The hypergraph duality problem Dual is defined as follows: given two simple hypergraphs G
and H, decide whether H consists precisely of all minimal transversals of G (in which case …

This article concerns the second-order systems U12 and V12 of bounded arithmetic, which
have proof-theoretic strengths corresponding to polynomial-space and exponential-time …

In 1990, Subramanian [1990] defined the complexity class CC as the set of problems log-
space reducible to the comparator circuit value problem (CCV). He and Mayr showed that …

Random 3CNF formulas constitute an important distribution for measuring the average-case
behavior of propositional proof systems. Lower bounds for random 3CNF refutations in many …

The (1+ 1) EA is a simple evolutionary algorithm that is known to be efficient on linear
functions and on some combinatorial optimization problems. In this paper, we rigorously …

We investigate the proof complexity of a class of propositional formulas expressing a
combinatorial principle known as the Kneser-Lovász Theorem. This is a family of …

Logic is playing an increasingly important role in the engineering of real-time, hybrid, and
cyber-physical systems, but mostly in the form of posterior verification and high-level …

We give a complete characterization of those categories which can arise as the subcategory
of total maps of a Turing category. A Turing category provides an abstract categorical setting …

This paper gives a novel approach to analyze SAT problem more deeply. First, I define new
elements of Boolean formula such as dominant variable, decision chain, and chain coupler …