5 ms·

There are 140 comments in the blog of Scot Aaronson about this topic: http://www.scottaaronson.com/blog/?p=2521#comments http://www.scottaaronson.com/blog/?p=2

by lovboat 11y ago

There are 140 comments in the blog of Scot Aaronson about this topic: http://www.scottaaronson.com/blog/?p=2521#comments http://www.scottaaronson.com/blog/?p=2521#comments Personal Opinion: Perhaps the Complexity Hierarchy is going to collapse since intuition is not so clear and perhaps the distance from P to NP is shrinking.

maweki 11y ago
This would mean that NP=Co-NP and that there is a polynomial certificate for every Co-NP problem. That is what breaks P=NP for me and I just can't wrap my head around how that would be possible.
- abetusk 11y ago
  Your comment is a little hard to parse. We could live in a world where there are short proofs that an NP-Complete problem is unsolvable but those short proofs are hard to find (i.e. NP=co-NP but P!=NP) [1]. I think there are other consequences but that's an area I don't know that much about. [1] http://cstheory.stackexchange.com/questions/8087/consequences-of-np-conp-and-p-ne-np http://cstheory.stackexchange.com/questions/8087/consequence...
  - maweki 11y ago
    Well, you've read my implication-arrow the wrong way. Since I don't believe that NP=co-NP (in any case), I can't believe that P=NP because Co-P=P. So if the collapse would happen (what the OP mentioned as a possibility), one implication would be NP=co-NP. I don't believe that so I can't believe in collapse.
abetusk 11y ago
I don't know why you would think this. There was strong empirical evidence (in my opinion) for thinking Graph Isomorphism was easy. NAUTY (and SAUCY) were good practical implementations that found solutions efficiently (except for some harder class of graphs, maybe). GI was known to be in NP and co-NP which is usually a red flag that the problem is not NP-Complete. For example, linear programming, integer polynomial factorization and primality testing were all in this NP and co-NP region (also discrete logarithm but that's still open). Though extremely informative, there's no reason that GI is polynomial (or pseudo polynomial) would give serious reason to believe that P is anywhere near NP.
- lmkg 11y ago
  > NAUTY (and SAUCY) were good practical implementations > that found solutions efficiently (except for some > harder class of graphs, maybe). There are good practical implementations of SAT solvers as well (except degenerate cases), even though SAT is the canonical NP-Complete problem.
  - abetusk 11y ago
    Fair enough, though I think the problem space is substantially different (though I didn't mention it above). It's much easier to make (random) 3-SAT difficult instances whereas for GI you needed highly structured graphs. Apparently Johnson graphs were one of the classes of graphs that caused people problems in GI.
    - wolfgke 11y ago
      There are other NP-complete problems, where really hard instances are a lot more rare.
- erik 11y ago
  I didn't think that GI was known to be in co-NP.
  - abetusk 11y ago
    Scott Aaronson's answer on MO indicates it was known under "suitable popular derandomization assumptions" [1]. [1] http://mathoverflow.net/a/32312 http://mathoverflow.net/a/32312
Ar-Curunir 11y ago
Lol. The polynomial hierarchy would collapse if GI was NP-Complete, but all efforts to prove that have failed. If anything, the distance from P to NP is growing.
- lovboat 11y ago
  You can shrink an interval [a,b] by two methods [a,b'] with b'<b or [a',b] with a'> a, what you see is [a,b'] (NP-complete seem easier or lower in the difficulty scale), what I see is [a',b] that is P cover a lot more ground, I think P will cover all NP-complete problems and then the interval becomes a unique point. If [P,NP-c] = [0,1] I see GI as 1/4, if GI is proven to be in P then I should say [P,NP-c] is now [1/4,1]. In order to reduce more that interval one should find a problem that people think has a probability of 0.5 to be in P and 0.5 to be in NP, if it is proven that problem is in P then the interval get reduced a lot more. Just trying to explain my perception of the intuitive complexity of algorithms.

by lovboat 11y ago

maweki 11y ago

This would mean that NP=Co-NP and that there is a polynomial certificate for every Co-NP problem. That is what breaks P=NP for me and I just can't wrap my head around how that would be possible.

abetusk 11y ago
Your comment is a little hard to parse. We could live in a world where there are short proofs that an NP-Complete problem is unsolvable but those short proofs are hard to find (i.e. NP=co-NP but P!=NP) [1]. I think there are other consequences but that's an area I don't know that much about. [1] http://cstheory.stackexchange.com/questions/8087/consequences-of-np-conp-and-p-ne-np http://cstheory.stackexchange.com/questions/8087/consequence...
- maweki 11y ago
  Well, you've read my implication-arrow the wrong way. Since I don't believe that NP=co-NP (in any case), I can't believe that P=NP because Co-P=P. So if the collapse would happen (what the OP mentioned as a possibility), one implication would be NP=co-NP. I don't believe that so I can't believe in collapse.

abetusk 11y ago

I don't know why you would think this. There was strong empirical evidence (in my opinion) for thinking Graph Isomorphism was easy. NAUTY (and SAUCY) were good practical implementations that found solutions efficiently (except for some harder class of graphs, maybe). GI was known to be in NP and co-NP which is usually a red flag that the problem is not NP-Complete. For example, linear programming, integer polynomial factorization and primality testing were all in this NP and co-NP region (also discrete logarithm but that's still open). Though extremely informative, there's no reason that GI is polynomial (or pseudo polynomial) would give serious reason to believe that P is anywhere near NP.

lmkg 11y ago
> NAUTY (and SAUCY) were good practical implementations > that found solutions efficiently (except for some > harder class of graphs, maybe). There are good practical implementations of SAT solvers as well (except degenerate cases), even though SAT is the canonical NP-Complete problem.
- abetusk 11y ago
  Fair enough, though I think the problem space is substantially different (though I didn't mention it above). It's much easier to make (random) 3-SAT difficult instances whereas for GI you needed highly structured graphs. Apparently Johnson graphs were one of the classes of graphs that caused people problems in GI.
  - wolfgke 11y ago
    There are other NP-complete problems, where really hard instances are a lot more rare.
erik 11y ago
I didn't think that GI was known to be in co-NP.
- abetusk 11y ago
  Scott Aaronson's answer on MO indicates it was known under "suitable popular derandomization assumptions" [1]. [1] http://mathoverflow.net/a/32312 http://mathoverflow.net/a/32312

Ar-Curunir 11y ago

Lol. The polynomial hierarchy would collapse if GI was NP-Complete, but all efforts to prove that have failed. If anything, the distance from P to NP is growing.

lovboat 11y ago
You can shrink an interval [a,b] by two methods [a,b'] with b'<b or [a',b] with a'> a, what you see is [a,b'] (NP-complete seem easier or lower in the difficulty scale), what I see is [a',b] that is P cover a lot more ground, I think P will cover all NP-complete problems and then the interval becomes a unique point. If [P,NP-c] = [0,1] I see GI as 1/4, if GI is proven to be in P then I should say [P,NP-c] is now [1/4,1]. In order to reduce more that interval one should find a problem that people think has a probability of 0.5 to be in P and 0.5 to be in NP, if it is proven that problem is in P then the interval get reduced a lot more. Just trying to explain my perception of the intuitive complexity of algorithms.