Computer Science – Computational Complexity
Scientific paper
2009-09-30
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
In this manuscript, assuming that Graedel's 1991 results are correct (which implies that bounds on the solution values for optimization problems can be expressed in existential second order logic where the first order part is universal Horn), I will show that Clique and Vertex Cover can be solved in polynomial time if the input structure is ordered and contains a successor predicate. In the last section, we will argue about the validity of Graedel's 1991 results. 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).
No associations
LandOfFree
Clique and Vertex Cover are solvable in polynomial time if the input structure is ordered and contains a successor predicate 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 Clique and Vertex Cover are solvable in polynomial time if the input structure is ordered and contains a successor predicate, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Clique and Vertex Cover are solvable in polynomial time if the input structure is ordered and contains a successor predicate will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-589251