We consider two signatures (sets of relational symbols) \(L_1\) and \(L_2\) . A map I that maps each finite \(L_1\) -structure to a finite \(L_2\) -structure is called an interpretation if for each \(L_1\) -structure M, the domain of \(I(M)\) is the disjoint union of powers of the domain of M and the relations of \(I(M)\) are defined by first-order formulas over the relations of M (the formulas do not depend on the special M). It has been shown that many reductions to NP-complete decision problems are interpretations. As examples, the problems Satisfiability, Clique, and Hamilton Cycle all are NP-complete via interpretations. Here, we show that also Graph Colouring and Exact Cover are complete in NP with respect to interpretations. It also could be shown that 3-Satisfiability is not NP-complete with respect to interpretations if it is described in a certain way as a class of finite structures If we model 3-Satisfiability the same way as the satisfiability problem then it is not trivially clear that it is not NP-complete through interpretations as reductions. In this article, we will show that 3-Satisfiability under this representation neither is NP-complete by interpretations. On the other hand, 3-Satisfiability can be modelled as a class of finite models that is defined by an existential second order formula with a universal first-order part. It will be shown that 3-Satisfiability is complete by quantifier-free interpretations in such classes of finite models. As consequence, also 3-colouring is complete in that class by quantifier-free interpretations. Also some variations of 3-Satisfiability are complete in that class by interpretations. It will be mentioned that interpretations can be used for trivial proofs that many NP-complete decision problems cannot be formulated in logics like Least-Fixed-Point.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

NP-completeness by First-order and Quantifier-free Interpretations and Related Topics

  • Elias Dahlhaus

摘要

We consider two signatures (sets of relational symbols) \(L_1\) and \(L_2\) . A map I that maps each finite \(L_1\) -structure to a finite \(L_2\) -structure is called an interpretation if for each \(L_1\) -structure M, the domain of \(I(M)\) is the disjoint union of powers of the domain of M and the relations of \(I(M)\) are defined by first-order formulas over the relations of M (the formulas do not depend on the special M). It has been shown that many reductions to NP-complete decision problems are interpretations. As examples, the problems Satisfiability, Clique, and Hamilton Cycle all are NP-complete via interpretations. Here, we show that also Graph Colouring and Exact Cover are complete in NP with respect to interpretations. It also could be shown that 3-Satisfiability is not NP-complete with respect to interpretations if it is described in a certain way as a class of finite structures If we model 3-Satisfiability the same way as the satisfiability problem then it is not trivially clear that it is not NP-complete through interpretations as reductions. In this article, we will show that 3-Satisfiability under this representation neither is NP-complete by interpretations. On the other hand, 3-Satisfiability can be modelled as a class of finite models that is defined by an existential second order formula with a universal first-order part. It will be shown that 3-Satisfiability is complete by quantifier-free interpretations in such classes of finite models. As consequence, also 3-colouring is complete in that class by quantifier-free interpretations. Also some variations of 3-Satisfiability are complete in that class by interpretations. It will be mentioned that interpretations can be used for trivial proofs that many NP-complete decision problems cannot be formulated in logics like Least-Fixed-Point.