2011/06/22 by Prabhu Manyem, Manyem, Prabhu
Computer Science · #03C13 #68Q15 #68Q17 #68Q19 #90C99 #Advanced Algebra and Logic #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.1.3 #F.4.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1106.4606
openalex publication_date 2011/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that ESO universal Horn logic (existential second logic where the\nfirst order part is a universal Horn formula) is insufficient to capture P, the\nclass of problems decidable in polynomial time. This statement is true in the\npresence of a successor relation in the input vocabulary. We provide two proofs\n--- one based on reduced products of two structures, and another based on\napproximability theory (the second proof is under the assumption that P is not\nthe same as NP). We show that the difference between the results here and those\nin Gr "adel (1991), is due to the fact that the expressions this paper deals\nwith are at the "structure level", whereas the expressions in Gr "adel (1991)\nare at the "machine level" --- a case of Easier done than said.\n