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

[Computational Complexity] Spares problems in NP thought to not be in P

Expand Messages
  • GASARCH
    (This post is similar to this old post. I am posting this anyway since when I first posted I made fundamental mistake. I fixed it the point I was trying to
    Message 1 of 1 , Jul 15, 2010
      (This post is similar to this old post. I am posting this anyway since when I first posted I made fundamental mistake. I fixed it the point I was trying to make get lost.)

      About once a semester I get asked
      What are the natural problems that are in NP, not known to be in P, and not known to be NPC? What is known about them?
      And I give the standard answers:
      1. Graph Isomorphism. If its NPC then PH collapses so it is though to NOT be NPC. There is no real consensus about its status with respect to P.
      2. Factoring. If its NPC then NP=coNP so it is thought to NOT be NPC. Most people think that it is NOT in P since people really want to solve this one and have not been able to. This is not a rigorous argument. Factoring is in QP. If quantum computers are ever practical then we may need to rethink how we think about these things.
      3. Discrete Log. Actually, are there reasons to think this is NOT NPC?
      The answer above are standard and I suspect most of my readers know them. However, there is a large source of problems that are in NP, likely not NPC, likely not in P, that people don't seem to talk about much: SPARSE PROBLEMS that are thought to be hard. The ones I know about are from Ramsey Theory. I give one example but there are many like it:

      {(1n,1m,c) : the n×m grid can be c-colored and not have any mono squares}

      1. This is clearly in NP since the coloring itself is the witness.
      2. Since this is a sparse set it is not NPC unless P=NP. (Actually it can be coded as a tally set.)
      3. I want to say People think this is hard. You may ask Name Three of Them! Indeed, the number of people who work on Computational Ramsey Theory is fairly small. However, Ramsey Theory itself has many people working on it and nobody has anything close to a result indicating that this problem is in P. I personally think that it is hard.
      4. For a fixed c there is a finite number of grids G1,...,Gp such that the n×m grid is c-colorable iff none of G1,...,Gp can fit inside the n×m grid. Hence, for fixed c, the problem is in P. (So the problem is Fixed Parameter Tractable.)
      5. Everything said above holds if you replace squares with rectangles or other configurations in the above.
      Questions:
      1. Are there other sparse problems in NP that we think are NOT in P? (that is, ones that DO NOT come from Ramsey Theory).
      2. Should we be teaching these in our complexity classes as examples of possible intermediary problems? The proof that they are likely not NPC is easy. However, to argue that these problems are likely not in P is hard. Also, these problems may appear unnatural to some students. (They may appear unnatural to some of my readers.)
      3. It is easy to argue that Factoring is probably not in P since you can point to the fact that people REALLY want to solve it quickly and so far have not. This is not a rigorous argument but I do count it as evidence. Is there a similar argument for GI? Is there a similar argument for my Ramsey Problems?
      4. Is there a mathematical reason to think that Factoring, GI, or my Ramsey Problems are not in P?


      --
      Posted By GASARCH to Computational Complexity at 7/15/2010 10:20:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.