3 citations · 3 across the 8 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.CC2009
Clique and Vertex Cover are solvable in polynomial time if the input structure is ordered and contains a successor predicate
Prabhu Manyem
In this manuscript, assuming that Graedel's 1991 results are correct (which implies that bounds on the solution values for optimization problems can be expressed in existential sec…
cs.LO2009
Lower Bounds on Syntactic Logic Expressions for Optimization Problems and Duality using Lagrangian Dual to characterize optimality conditions
Prabhu Manyem
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 differenc…