ESO universal Horn and LFP logics: separation between machine level and structure level

Details ESO universal Horn and LFP logics: separation between machine level and structure level ESO universal Horn and LFP logics: separation between machine level and structure level

2011-06-23

arxiv.org/abs/1106.4606v4

Computer Science

Computational Complexity

Scientific paper

Consider decision problems derived from optimization problems. For problems in this category, we show that they cannot be expressed in existential second order (ESO) logic with a first order part that is universal Horn (or simply, ESO \Pi_1 Horn) at the structure level, as opposed to machine level. This is true even when we consider ordered structures. We show that an NP-complete problem (Maximum Independent Set) and a polynomially solvable problem (Maximum Matching) have identical ESO \Pi_1 (non-Horn) expressions when the only unknowns are the second order predicates, hence this logic is too weak to distinguish between the two classes. At the structure level, Fagin's theorem is false in one sense, in that ESO universal sentences under ordered structures cannot capture the class NP. Also at the structure level, under ordered structures, least fixed point logic with counting (LFP+C) is insufficient to capture P, the class of problems decidable in polynomial time.

Affiliated with

Also associated with

No associations

Rating

ESO universal Horn and LFP logics: separation between machine level and structure level 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 ESO universal Horn and LFP logics: separation between machine level and structure level, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and ESO universal Horn and LFP logics: separation between machine level and structure level will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-469339