2009/09/30 by Prabhu Manyem, Manyem, Prabhu
Computer Science · #Advanced Algebra and Logic #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.0909.5521
openalex publication_date 2009/09/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this manuscript, assuming that Graedel's 1991 results are correct (which\nimplies that bounds on the solution values for optimization problems can be\nexpressed in existential second order logic where the first order part is\nuniversal Horn), I will show that Clique and Vertex Cover can be solved in\npolynomial time if the input structure is ordered and contains a successor\npredicate. In the last section, we will argue about the validity of Graedel's\n1991 results. Update: Manuscript withdrawn, because results are incorrect. If\nphi = phi1 AND phi2, and phi is a Horn formula, it does NOT mean that both\nphi1 and phi2 are Horn formulae. Furthermore, the cardinality constraint\nCANNOT be expressed as a universal Horn sentence in ESO (NOT even when the\nstructure is ordered).\n