I recently got an email that said roughly the following:
Hi Bill,
I am a grad student in combinatorial optimization, and I have a
question that I was hoping you could answer: does "FOO is
APXcomplete" imply "FOO is MAX SNPcomplete", viceversa, or neither?
To be honest this might be very simple... but given that this is
essentially the domain of computational complexity I was hoping that
either you would know the answer, or otherwise that your blog's
readers might have some suggestions. (Basically your blog is currently
the main source of computational complexity to my brain, so it seemed
natural to ask you when I became confused.)
My impressions from reading up are the following:

APX is the subset of NP optimization problems with constantfactor
polytime approximations

MAX SNP has a much more complicated definition

APX contains MAX SNP but I don't know if the containment is known to be strict
To motivate my question, many papers say "the FOO problem is MAX
SNPhard and also APXhard" but is there currently a point in stating
both? As I researched the topic, I found that the reductions allowed
in the definition of "APXhard" and "MAX SNPhard" are apparently
slightly different... and around here my confusion set in.
One compendium, at least, uses simply "APXhard" by convention:
here
I hope this is up your alley, but if not then no worries.
Sincerely,
NAME DELETED FOR THIS BLOG POSTING
This email raises several questions and metaquestions

The question on APX might be interesting.

Is this a HW question? Is she cheating on it by asking me?
Should I answer it? My inclination on this one is that
its NOT a HW, it is legit. However, I don't know the
answer, but if one of you does, by all means post
(she knows I am posting this to the blog).
By contrast, someone once
posted to a readnews group (remember those?)
Someone out there please help me with this problem:
why is {a^n  n prime} not regular? I'm not a student
asking for the solution to HW 4, problem 2. Honest I'm not!!
Looks like a student doing a HW problem.

``your blog is my main source for complexity theory''
A scary thought. She needs to get more sources like
Luca and Scott's blog. Or maybe books (remember those?).
This is a legit question, probably coming from an undergrad (or starting PhD student) starting to read about inapproximability.
ReplyDeleteThe problem MAX3SAT is MAXSNPcomplete via Lreductions, and APXcomplete via APreductions.
ReplyDeletehttp://books.google.com/books?id=_C8Ly1ya4cgC&pg=PA22&lpg=PA22&dq=max+snp+apx&source=web&ots=mGa6hQZVnz&sig=Cpugt4sQtxNDC4OZl9Wi8hstQ#PPA22,M1
Would it be a good idea to set up a bulletin board (is there already one?) for Complexity (and in general, Theoretical CS) related questions? From personal experience, a google search while trying to solve a computer technology related question (say on programming, installing and using stuff, system administration, and so on), is very likely to turn up the answer, if it exists, on a bulletin board somewhere. Perhaps a theoryrelated BB would be a good resource to have.
ReplyDeleteI have in fact been thinking about setting one up for some time now, but was not sure about whether it would help or be a nuisance  the homework issue,spam/flame, etc  to the theory community.
(Basically your blog is currently the main source of computational complexity vox populi to my brain, so it seemed natural ...)
Philip
Hey Bill,
ReplyDeleteI thought you might like this given your like of Dylan parodies.
http://www.youtube.com/watch?v=Nej4xJe4Tdg
All problems in MAXSNP can be constantfactor approximated. But MAXSNP contains, by definition, only maximization problems. Thus, APX strictly contains MAXSNP.
ReplyDeleteHowever, other problems, like minimization problem, can be "placed" in MAXSNP via reduction to a MAXSNP problem. The closure of MAXSNP under Lreductions (introduced by Papadimitriou and Yannakakis when they defined MAXSNP) is exactly APXPB, which is the class of all polynomially bounded problems in APX.
If we use PTASreductions instead of Lreductions, then APX is equal to the closure of MAXSNP.
(See Khanna et al., On syntactic versus computational views of approximability, SIAM J. Comput. 28, 1998.)
Thanks for the comments. The max vs min issue I did not realize before, but it does not seem central, and I still don't really have the answers I really wanted:
ReplyDeletea) are the statements "FOO is an APX maximization problem" and "FOO is a MAXSNP maximization problem" related (does one imply the other?)
b) same, !@$#$ > !@$#$hard
c) same, !@$#$ > !@$#$complete
Thanks,
Anonymous
Pardon my mistake... since MAX SNP is a subset of APX the answer to a) is partially determined
ReplyDeleteGiven what is known it is immediate that every MAXSNPhard problem (under Lreductions) is also APXhard (under APreductions). However, simce MAXSNP is a proper subset of APX (because of the min/max issue) and likely a proper subset of the APX maximization problems (though we don't know this for sure since both might be contained in FP), the MAXSNPcomplete problems are a proper subset of the APXcomplete problems and likely of the APXcomplete maximization problems. Moreover, even within MAXSNP it is quite possible that this also holds since the APreductions are more liberal than Lreductions. This last question seems the only one where we don't have a natural answer.
ReplyDeleteFor those asking for a BB for computer theory, you can check out the Usenet newsgroup comp.theory.
ReplyDeleteGiven what is known it is immediate that every MAXSNPhard problem (under Lreductions) is also APXhard (under APreductions).
ReplyDeleteThis seems tricky, at least in trying to use a crude analogy I have got stuck. (Assume we care only about maximization problems). Since
MAX SNP subset APX
it seems that every APX hard problem should be MAX SNP hard, not viceversa. The analogy is that
P subset EXP
and every EXP hard problem is P hard...
Anonymous 10: Think about it a little harder.
ReplyDelete