HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Are there any problems in $APX - PTAS$ that are not $APX$-complete?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
areanyproblemscompletethatapxtherenotptas

Problem

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$.

Solution

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.

Context

StackExchange Computer Science Q#12112, answer score: 7

Revisions (0)

No revisions yet.