Computer Science – Computational Complexity
Scientific paper
2010-04-11
Computer Science
Computational Complexity
Manuscript withdrawn, because results are incorrect. If phi = phi_1 AND phi_2, and phi is a Horn formula, it does NOT mean tha
Scientific paper
We show that the maximum clique problem (decision version) can be expressed in existential second order (ESO) logic, where the first order part is a Horn formula in second-order quantified predicates. Without ordering, the first order part is $\Pi_2$ Horn; if ordering is used, then it is universal Horn (in which case, the second order variables can be determined in polynomial time). UPDATE: Manuscript withdrawn, because results are incorrect. If phi = phi_1 AND phi_2, and phi is a Horn formula, it does NOT mean that both phi_1 and phi_2 are Horn formulae. Furthermore, the cardinality constraint CANNOT be expressed as a universal Horn sentence in ESO (NOT even when the structure is ordered). Graedel's theorem is valid at a lower (machine) level, but probably NOT at a higher level.
No associations
LandOfFree
Existential Second Order Logic Expression With Horn First Order for Maximum Clique (Decision Version) 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 Existential Second Order Logic Expression With Horn First Order for Maximum Clique (Decision Version), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Existential Second Order Logic Expression With Horn First Order for Maximum Clique (Decision Version) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-186890