Showing cs.CCShow all
3 papers · 1 filter
cs.CC2007
A Reply to Hofman On: "Why LP cannot solve large instances of NP-complete problems in polynomial time"
Moustapha Diaby
Using an approach that seems to be patterned after that of Yannakakis, Hofman argues that an NP-complete problem cannot be formulated as a polynomial bounded-sized linear programmi…
cs.CC2006
On "P = NP: Linear Programming Formulation of the Traveling Salesman Problem": A reply to Hofman's Claim of a "Counter-Example"
Moustapha Diaby
We show that Hofman's claim of a "counter-example" to Diaby's LP formulation of the TSP is invalid.
cs.CC2006★ 1 cited
Equality of complexity classes P and NP: Linear programming formulation of the quadratic assignment problem
Moustapha Diaby
In this paper, we present a polynomial-sized linear programming formulation of the Quadratic Assignment Problem (QAP). The proposed linear program is a network flow-based model. He…