CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Approximate Algorithms For NP-Complete Problems

1. Junior Member
Join Date
Jan 2009
Posts
5

## Approximate Algorithms For NP-Complete Problems

I have a question about approximate algorithms for known NP-Complete problems.

I know that if you find an answer for an NP complete problem, that means you can find an answer for any problem that has been reduced to it, but not necessarily for any problem that is has been reduced to. I think that is correct at least.

If you have an algorithm that finds an approximate answer for an NP-Complete problem, does this mean that you can find an approximate answer for all problems that have been reduced to it or problems that it has been reduced to?

For example, Imagine that you constructed an approximation algorithm for the Traveling Salesman Problem that could always calculate a solution that is correct within a factor of 1/k of the optimal tour in O(n ⋅2^k) time. Would you be able to use this approximation algorithm to obtain a “good” solution to all other NP-Complete problems?

I'm thinking no. Proving a problem NP complete with a reduction only ensures that an exact answer correlates to another exact answer. You cannot make the same assumption about an approximate answer.

Even if it is possible, I think it will only give an approximate answer for problems that have been reduced to the TSP, and it will not given an approximate answer for problems that the TSP has been reduced to.

Any thoughts? I really can't convince myself of a correct answer to this question. Thanks in advance!

2. Elite Member
Join Date
May 2009
Posts
2,413

## Re: Approximate Algorithms For NP-Complete Problems

Originally Posted by lesnaubr
If you have an algorithm that finds an approximate answer for an NP-Complete problem, does this mean that you can find an approximate answer for all problems that have been reduced to it or problems that it has been reduced to?
Not generally but there is a class of very hard NP-hard problems (I think it's called MAX SNP) for which no approximation in P exists. If you do find such an approximation then P = NP.

3. Junior Member
Join Date
Jan 2009
Posts
5

## Re: Approximate Algorithms For NP-Complete Problems

Originally Posted by nuzzle
Not generally but there is a class of very hard NP-hard problems (I think it's called MAX SNP) for which no approximation in P exists. If you do find such an approximation then P = NP.
So it sounds like I am correct in assuming that an approximate answer for a certain problem does not guarantee an approximate answer for a problem it has been reduced from or to.

Is there a difference for problems it have been reduced from or problems that it has been reduced to?

4. Elite Member
Join Date
May 2009
Posts
2,413

## Re: Approximate Algorithms For NP-Complete Problems

Originally Posted by lesnaubr
So it sounds like I am correct in assuming that an approximate answer for a certain problem does not guarantee an approximate answer for a problem it has been reduced from or to.

Is there a difference for problems it have been reduced from or problems that it has been reduced to?
I'm not so sure about that. If a problem can be reduced to another problem this indicates both are equally hard so if an approximate solution exists for one it should also exist for the other.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Click Here to Expand Forum to Full Width

On-Demand Webinars (sponsored)

×
We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.