ISSN:
1433-0490
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract In this paper we investigate the logics obtained by augmenting first-order logic (with successor) with operators corresponding to some decision problems complete forNP via logspace reductions. We show that our encodings of the Satisfiability Problem and the 3-Colourability Problem, namely SAT and 3COL, respectively (as sets of finite structures over specific vocabularies), are complete forNP via projection translations (very weak reductions between problems): the fact that an encoding of the Satisfiability Problem (resp. the 3-Satisfiability Problem) is (resp. not) complete forNP via interpretative reductions (again, very weak reductions) had been shown previously by Dahlhaus. It is unknown whether our encoding of the 3-Satisfiability Problem, namely 3SAT, is complete forNP 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 instance has at most three literals in each clause (as opposed to exactly three literals), namely ≤ 3SAT, then we show that ≤3SAT is complete forNP via projection translations. 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 forNP via projection translations differs extremely from the proof of Dahlhaus that SAT is complete forNP via interpretative reductions, as he relies on Fagin's well-known characterization ofNP whereas our results do not: indeed, they give Fagin's result as a corollary. We use the problem 3COL to show the difference between interpretative reductions and projection translations as we show that 3COL is complete forNP via the latter but not via the former. The logics mentioned above are shown to be similar in expressibility but are shown to be much more expressible than that formed by extending first-order logic with an operator corresponding to the Hamiltonian path problem for digraphs (assumingNP ≠co-NP).
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01195200
