A Reply to Hofman On: "Why LP cannot solve large instances of NP-complete problems in polynomial time"

Details A Reply to Hofman On: "Why LP cannot solve large instances of NP-complete problems in polynomial time" A Reply to Hofman On: "Why LP cannot solve large instances of NP-complete problems in polynomial time"

2007-01-03

arxiv.org/abs/cs/0701014v2

Computer Science

Computational Complexity

2 page; 1 table; clarification of some unclear statements

Scientific paper

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 programming problem. He then goes on to propose a "construct" that he claims to be a counter-example to recently published linear programming formulations of the Traveling Salesman Problem (TSP) and the Quadratic Assignment Problems (QAP), respectively. In this paper, we show that Hofman's construct is flawed, and provide further proof that his "counter-example" is invalid.

Affiliated with

Also associated with

No associations

Rating

A Reply to Hofman On: "Why LP cannot solve large instances of NP-complete problems in polynomial time" 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 A Reply to Hofman On: "Why LP cannot solve large instances of NP-complete problems in polynomial time", we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Reply to Hofman On: "Why LP cannot solve large instances of NP-complete problems in polynomial time" will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-563653