Logical Description of Monotone NP Problems
Iain A. Stewart · Journal of Logic and Computation · 1994
We introduce the class of problems NPC-RAT accepted by polynomial time (nondeterministic) conjunctive random-access Turing machines (C-RATs): such machines crash when the oracle answers ‘no’ (the oracle is always the input structure). We show that NPC-RAT consists of all monotone problems in NP and we logically characterize this complexity class in two ways: the first involves an extension of first-order logic using an operator corresponding to some problem (an approach initiated by Immerman); the second involves a restricted version of existential second-order logic (in the style of Fagin). In both logics, symbols belonging to the problem vocabulary are only allowed to occur positively. We also show that NPC-RAT possesses complete problems via monotone projection translations. It had previously been shown that certain complete problems for NP (via logspace reductions) are unlikely to be complete for NP via monotone projection translations.