Thursday, September 13, 2007

Question and Metaquestion about Students emailing you problems

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:
  1. APX is the subset of NP optimization problems with constant-factor polytime approximations
  2. MAX SNP has a much more complicated definition
  3. 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.


This email raises several questions and metaquestions
  1. The question on APX might be interesting.
  2. 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.
  3. ``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?).


  1. This is a legit question, probably coming from an undergrad (or starting PhD student) starting to read about inapproximability.

  2. The problem MAX3SAT is MAX-SNP-complete via L-reductions, and APX-complete via AP-reductions.,M1

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

    I 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 ...)


  4. Hey Bill,

    I thought you might like this given your like of Dylan parodies.

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

    However, 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.)

  6. 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:

    a) 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


  7. Pardon my mistake... since MAX SNP is a subset of APX the answer to a) is partially determined

  8. Given 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.

  9. For those asking for a BB for computer theory, you can check out the Usenet newsgroup comp.theory.

  10. Given what is known it is immediate that every MAXSNP-hard problem (under L-reductions) is also APX-hard (under AP-reductions).

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

  11. Anonymous 10: Think about it a little harder.