Using the Hamiltonian path operator to capture NP

摘要

In this paper, we define the language (FO + posHP), where HP is the Hamiltonian path operator, and show that a problem can be represented by a sentence of this language if and only if the problem is in NP. We also show that every sentence of this language can be written in a normal form, and this normal form theorem establishes that the problem of deciding whether there is a directed Hamiltonian path between two distinguished vertices in a digraph is complete for NP via projection translations, where these translations are apparently much weaker than logspace reductions: as far as we know, this is the first such problem discovered. We also give a general technique for extending existing languages using operators derived from problems.