Comparing the Expressibility of Languages Formed Using NP-Complete Operators

Abstract

In this paper, we consider extending the first-order language FO by the operator 3COL, corresponding to the problem of deciding whether a graph can be properly coloured using at most three colours, just as FO has, in the past, been extended by the operators DTC, STC, TC, ATC, and HP: in particular, HP is the operator corresponding to the problem of deciding whether a digraph has a directed Hamiltonian path between two distinguished vertices. We find that if the language (FO + pos3COL) has the same expressibility as the (seemingly comparable) language (FO+posHP), then NP= co-NP; perhaps a surprising result given that both the problems HP and 3COL are NP-complete via logspace reductions. We show that the problem 3COL is complete for the complexity class $FO1pos3COL$ (a sub-class of NP) via projection translations, but it is open as to whether $FO1pos3COL$ coincides with NP. We also present general techniques which might be used to show that other languages capture NP and other problems are complete for NP via projection translations.