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
APX-complete" imply "FOO is MAX SNP-complete", vice-versa, 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 constant-factor
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
SNP-hard and also APX-hard" but is there currently a point in stating
both? As I researched the topic, I found that the reductions allowed
in the definition of "APX-hard" and "MAX SNP-hard" are apparently
slightly different... and around here my confusion set in.
One compendium, at least, uses simply "APX-hard" 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 MAX-SNP-complete via L-reductions, and APX-complete via AP-reductions.
ReplyDeletehttp://books.google.com/books?id=_C8Ly1ya4cgC&pg=PA22&lpg=PA22&dq=max+snp+apx&source=web&ots=mGa6hQZVnz&sig=Cpugt4sQ-t-xNDC4OZl9Wi8hstQ#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 theory-related 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 MAX-SNP can be constant-factor approximated. But MAX-SNP contains, by definition, only maximization problems. Thus, APX strictly contains MAX-SNP.
ReplyDeleteHowever, other problems, like minimization problem, can be "placed" in MAX-SNP via reduction to a MAX-SNP problem. The closure of MAX-SNP under L-reductions (introduced by Papadimitriou and Yannakakis when they defined MAX-SNP) is exactly APX-PB, which is the class of all polynomially bounded problems in APX.
If we use PTAS-reductions instead of L-reductions, then APX is equal to the closure of MAX-SNP.
(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 MAX-SNP 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 MAXSNP-hard problem (under L-reductions) is also APX-hard (under AP-reductions). 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 MAXSNP-complete problems are a proper subset of the APX-complete problems and likely of the APX-complete maximization problems. Moreover, even within MAXSNP it is quite possible that this also holds since the AP-reductions are more liberal than L-reductions. 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 MAXSNP-hard problem (under L-reductions) is also APX-hard (under AP-reductions).
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 vice-versa. The analogy is that
P subset EXP
and every EXP hard problem is P hard...
Anonymous 10: Think about it a little harder.
ReplyDelete