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
