In this paper, we consider extending the first-order languageFOby the operator3COL, corresponding to the problem of deciding whether a graph can be properly coloured using at most three colours, just asFOhas, in the past, been extended by the operatorsDTC,STC,TC,ATC, andHP:in particular,HPis 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 problemsHPand3COLare NP-complete via logspace reductions. We show that the problem3COLis complete for the complexity classFO1pos3COL(a sub-class of NP) via projection translations, but it is open as to whetherFO1pos3COLcoincides 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.
展开▼
