On Canonical Forms of Complete Problems via First-order Projections

Details On Canonical Forms of Complete Problems via First-order Projections On Canonical Forms of Complete Problems via First-order Projections

2007-06-22

arxiv.org/abs/0706.3412v1

Computer Science

Computational Complexity

9 pages

Scientific paper

The class of problems complete for NP via first-order reductions is known to be characterized by existential second-order sentences of a fixed form. All such sentences are built around the so-called generalized IS-form of the sentence that defines Independent-Set. This result can also be understood as that every sentence that defines a NP-complete problem P can be decomposed in two disjuncts such that the first one characterizes a fragment of P as hard as Independent-Set and the second the rest of P. That is, a decomposition that divides every such sentence into a quotient and residue modulo Independent-Set. In this paper, we show that this result can be generalized over a wide collection of complexity classes, including the so-called nice classes. Moreover, we show that such decomposition can be done for any complete problem with respect to the given class, and that two such decompositions are non-equivalent in general. Interestingly, our results are based on simple and well-known properties of first-order reductions.ow that this result can be generalized over a wide collection of complexity classes, including the so-called nice classes. Moreover, we show that such decomposition can be done for any complete problem with respect to the given class, and that two such decompositions are non-equivalent in general. Interestingly, our results are based on simple and well-known properties of first-order reductions.

Affiliated with

Also associated with

No associations

Rating

On Canonical Forms of Complete Problems via First-order Projections does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Canonical Forms of Complete Problems via First-order Projections, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Canonical Forms of Complete Problems via First-order Projections will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-177948