Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap

Abstract

We show that simple syntactic expressions such as existential second-order (ESO) universal Horn formulae can express NP-hard optimization problems. There is a significant difference between the expressibilities of decision problems and optimization 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 optimization version in NP-hard. It is known that all polynomially solvable decision problems can be expressed as ESO universal (Π₁) Horn sentences in the presence of a successor relation. We show here that, on the other hand, if P ≠ NP, optimization problems defy such a characterisation, by demonstrating that even a Π₀ (quantifier free) Horn formula is unable to guarantee polynomial time solvability. Finally, by connecting concepts in optimization duality with those in descriptive complexity, we will show a method by which optimization problems can be solved by a single call to a ‘decision’ Turing machine, as opposed to multiple calls using a classical binary search setting.

Keywords:

• optimization
• duality
• computational complexity
• descriptive complexity
• decision problem
• MaxHorn2Sat

Acknowledgements

I thank James Gate and Iain Stewart at the University of Durham (UK) for motivating me towards this line of research. A part of this work was carried out while I was visiting the National Cheng Kung University (NCKU) in Taiwan on a visiting fellowship; support from NCKU is gratefully acknowledged. Research also supported by grants from the National Natural Science Foundation of China (No. 11071158) and the Key Disciplines of Shanghai Municipality (No. S30104). Last, but not the least, comments and suggestions from the referees have been very helpful.

Notes

Notes

1. Of course, when it comes to computer representation, rational numbers will be used.

2. Strictly speaking, we should use |I| here, where |I| is the length of the representation of I. However, |I| is polynomial in |A|, hence we can use |A|.

3. 256 may be ‘large’, but still a finite number.

4. Defined in Definition 8.

5. For a graph problem, an algorithm is strongly polynomial if the running time is a polynomial in the number of vertices and/or edges; it becomes weakly polynomial if the running time is a polynomial in the logarithm of edge weights. In Linear Programming, this translates to the number of variables/constraints versus the data in the coefficient matrix A and the right side vector b. In the graph problem, the number of vertices/edges represents the number of input parameters, whereas the edge weights represent the values of such parameters.

6. The first-order predicates are part of the input, hence their truth values are known and can be substituted.

7. A word of caution – feasible solutions, a difference in terminology: Fagin 6 and Grädel 10 have syntactically characterized feasible solutions for classes NP and P, respectively. However the ‘feasibility’ captured by an ESO expression, as described by Fagin and Grädel, also includes an upper (lower) bound on the objective function of a minimization (maximization) problem, such as f ₁(x) ≥ K where K is a constant – not just satisfaction of the constraints such as Ax ≤ b, x ≥ 0 in (18). In this article, we differ from this view; when we talk about feasibility, we only refer to satisfaction of constraints such as Ax ≤ b, x ≥ 0.