2009/04/28 by Prabhu Manyem, Manyem, Prabhu
Computer Science · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.CC #cs.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0904.4331
An expansion of the previous version to include: a single call to a decision Turing machine to solve optimization problems obeying strong duality in polynomial time
openalex publication_date 2009/04/28 · arxiv created 2011/07/24 · arxiv updated 2011/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that simple syntactic expressions such as existential second order (ESO) universal Horn formulae can express NP-hard optimisation problems. There is a significant difference between the expressibilities of decision problems and optimisation problems. This is similar to the difference in computation times for the two classes of problems; for example, a 2SAT Horn formula can be satisfied in polynomial time, whereas the optimisation version in NP-hard. It is known that all polynomially solvable decision problems can be expressed as ESO universal (Π1) Horn sentences in the presence of a successor relation. We show here that, on the other hand, if P ≠ NP, optimisation problems defy such a characterisation, by demonstrating that even a Π0 (quantifier free) Horn formula is unable to guarantee polynomial time solvability. Finally, by connecting concepts in optimisation duality with those in descriptive complexity, we will show a method by which optimisation problems can be solved by a single call to a "decision" Turing machine, as opposed to multiple calls using a classical binary search setting.