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:
- 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.
- 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.
- Discrete Log. Actually, are there reasons to think this is NOT NPC?
{(1n,1m,c) : the n×m grid can be c-colored and not have any mono squares}
- This is clearly in NP since the coloring itself is the witness.
- Since this is a sparse set it is not NPC unless P=NP. (Actually it can be coded as a tally set.)
- 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.
- 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.)
- Everything said above holds if you replace squares with rectangles or other configurations in the above.
- Are there other sparse problems in NP that we think are NOT in P? (that is, ones that DO NOT come from Ramsey Theory).
- 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.)
- 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?
- Is there a mathematical reason to think that Factoring, GI, or my Ramsey Problems are not in P?
Let me ask a silly question: Mahaney Theorem says "if a sparse set is NP-complete, then P=NP". Is there anything known about "if a sparse set is not in P, then ???" ?
ReplyDeleteHow about the padded version of any natural NEXP-complete set? But maybe padded versions of natural languages no longer count as natural?
ReplyDelete@Lance: whoops. Just saw your comment.
ReplyDeleteHartmanis-Immerman-Sewelson (1985): There are no sparse sets in NP-P iff E=NE (reference)
ReplyDelete> Discrete Log. Actually, are there reasons to think this is NOT NPC?
ReplyDeleteWhat is the decision version of your DLOG problem? Let's consider this version: Given a prime p, a generator g of (Z/pZ)^* and two numbers a and b in {1,...,p-1}, is the unique i such that a = g^i mod p smaller than b? An oracle to this problem lets you find discrete logs by binary search.
This problem is clearly in NP and is also in co-NP because if the unique such i is not smaller than b then you can guess it and verify it.
If you are worried about the promise in the input that g is a generator of (Z/pZ)^*, please note that this promise can also be checked in NP \cap co-NP: for a certificate that g is a generator guess the factorization of p-1 and check that g^{(p-1)/q} \not= 1 mod p for every prime factor q of p-1, and for a certificate that g is not a generator guess some i < p-1 such that g^i \not= 1 mod p.
B.--there are plenty of sparse sets provably not in P. For instance, a random subset of 1^*, the all-ones strings.
ReplyDeleteForgive me if this is to far off track- but this discussion brings to mind a problem that has disturbed me for a while. It is not quite sparse, but it feels similar in that it has very little expressive power (there for it is hard to use it as a target of a reduction). Given: a set of linear inequalities and a set of points- do they represent the same convex set? Anyone know the state of this problem? The problem has a easy co-structure (just show one of the vertices violates an inequality or exhibit a new feasible point not in the convex hull of the vertices) but I don't know of prove the affirmative method.
ReplyDeleteDiscrete Log sits in BQP (and in NP \intersect co-NP as explained above), so all the Factoring arguments apply to dlog as well.
ReplyDelete@John: I am not totally sure but maybe the answer to your question can be deduced from
ReplyDeletehttp://www.springerlink.com/content/9273811760307743/
To me, the people who desperately want to factor, don't come into the equation at all. They are practical people and would be satisfied by an exponential algorithm provided the runtime was still fast enough (tiny coefficient in front of a barely-bigger-than-1-base exponent) to easily crack RSA. And conversely they'd be displeased with a polynomial-time algorithm if the degree of the polynomial was 5000 digits. So there's very little real relation...
ReplyDelete