We introduce the class of problems NPC-RATaccepted 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-RATconsists 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-RATpossesses 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 translati
展开▼
