[Solved]: Are there any problems in $APX - PTAS$ that are not $APX$-complete?

Problem Detail: 

I have a question about the structure of the complexity class $APX$. Obviously, unless $P=NP$, no problem in the class $PTAS$ can be $APX$-complete (under the AP-reduction). However, what about the rest of problems in $APX$? Are there any problems known that are in $APX$, do not have a $PTAS$ (unless $P=NP$) and at the same time are provably not $APX$-complete (unless $P=NP$)?

For the class $NP$, Ladner's Theorem guarantees the existence of problems in $NP - P$ that are not $NP$-complete (unless $P=NP$) - the so-called $NP$-intermediate problems. I am curious if any similar result has been proved for $APX - PTAS$ with respect to approximation preserving reductions.

It is possible that the answer to this question is trivial - to be honest, the only $APX$-complete problem I know is MAX-3-SAT. However, I wonder how hard it is with respect to other problems in $APX - PTAS$.

Asked By : 042

Answered By : Luke Mathieson

Yes, at least under some reasonable assumptions. Crescenzi, Kann, Silverstri & Trevisan show that Minimum Bin Packing, Mininum Degree Spanning Tree and Minimum Edge Coloring are APX-intermediate unless the polynomial hierarchy collapses.

Considering that the paper is from 1996, I'm sure there's now a significantly larger number of known APX-intermediate problems.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12112

 Ask a Question

 Download Related Notes/Documents