Lower Bounds on Syntactic Logic Expressions for Optimization Problems and Duality using Lagrangian Dual to characterize optimality conditions

Details Lower Bounds on Syntactic Logic Expressions for Optimization Problems and Duality using Lagrangian Dual to characterize optimality conditions Lower Bounds on Syntactic Logic Expressions for Optimization Problems and Duality using Lagrangian Dual to characterize optimality conditions

2009-04-28

arxiv.org/abs/0904.4331v3

Computer Science

Logic in Computer Science

An expansion of the previous version to include: a single call to a decision Turing machine to solve optimization problems obe

Scientific paper

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 ($\Pi_1$) Horn sentences in the presence of a successor relation. We show here that, on the other hand, if $P \neq NP$, optimisation problems defy such a characterisation, by demonstrating that even a $\Pi_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.

Affiliated with

Also associated with

No associations

Rating

Lower Bounds on Syntactic Logic Expressions for Optimization Problems and Duality using Lagrangian Dual to characterize optimality conditions 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 Lower Bounds on Syntactic Logic Expressions for Optimization Problems and Duality using Lagrangian Dual to characterize optimality conditions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower Bounds on Syntactic Logic Expressions for Optimization Problems and Duality using Lagrangian Dual to characterize optimality conditions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-712899