ON COMPLETENESS FOR NP VIA PROJECTION TRANSLATIONS

In this paper we investigate the logics obtained by augmenting first-o rder logic (with successor) with operators corresponding to some decis ion problems complete for NP via logspace reductions. We show that our encodings of the Satisfiability Problem and the 3-Colourability Probl em, namely SAT and 3COL, respectively (as sets of finite structures ov er specific vocabularies), are complete for NP via projection translat ions (very weak reductions between problems): the fact that an encodin g of the Satisfiability Problem (resp. the 3-Satisfiability Problem) i s (resp. not) complete for NP via interpretative reductions (again, ve ry weak reductions) had been shown previously by Dahlhaus. It is unkno wn whether our encoding of the 3-Satisfiability Problem, namely 3SAT, is complete for NP via projection translations, although we show that it is for iterated projection translations. However, if we consider an encoding of the version of the 3-Satisfiability Problem where each in stance has at most three literals in each clause (as opposed to exactl y three literals), namely less than or equal to 3SAT, then we show tha t less than or equal to 3SAT is complete for NP via projection transla tions. It appears to matter as to how we encode a decision problem as a set of finite structures over some vocabulary when considering weak reductions such as ours. Our proof that SAT is complete for NP via pro jection translations differs extremely from the proof of Dahlhaus that SAT is complete for NP via interpretative reductions, as he relies on Fagin's well-known characterization of NP whereas our results do not: indeed, they give Fagin's result as a corollary. We use the problem 3 COL to show the difference between interpretative reductions and proje ction translations as we show that 3COL is complete for NP via the lat ter but not via the former. The logics mentioned above are shown to be similar in expressibility but are shown to be much more expressible t han that formed by extending first-order logic with an operator corres ponding to the Hamiltonian path problem for digraphs (assuming NP not equal co-NP).