Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Question and Metaquestion about Students emailing ...

Expand Messages
  • GASARCH
    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
    Message 1 of 1 , Sep 13, 2007
    • 0 Attachment
      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.

      Sincerely,

      NAME DELETED FOR THIS BLOG POSTING
      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?).


      --
      Posted By GASARCH to Computational Complexity at 9/13/2007 10:53:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.