Logical description of monotone NP problems

We introduce the class of problems NP ( \RAJ accepted by polynomial time (nondetermirustic) 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.RXT 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 translation