Friday, November 11, 2011

My response to the Gasarch P vs NP poll

A while back GASARCH solicited responses to a P vs NP poll and gave Oct 31 as the deadline. Now that the deadline is passed I post my answers.
  1. Does P=NP? I think P is NOT NP. However, I am not dogmatic on this. When I first saw the Graph Minor Theorem used to get Vertex Cover for fixed k into O(n3) times I thought that a different very-hard-math-thing-that-I-don't-understand might be able to get SAT in P. Also, I am more convinced that separating the two is hard then I am convinced that they are different. Litmus test: If someone told me that the problem had been solved, but not which direction, I would guess P=NP. SIDE NOTE: My wife thinks P is NOT NP since If P=NP then they would have proven it by now. This argument may become more compelling as time goes on.
  2. When do you think it will be resolved? Between 200 and 400 years from now. Jon Katz told me: If its not solved within 200 years its not going to be solved..
  3. What kinds of techniques will be used?
    1. Fermat didn't know about Elliptic Curves. Similarly, we do not know the techniques.
    2. I hope its Ramsey Theory and Logic so I might understand the proof.
    3. If it comes out of Geometric Complexity Theory I will not understand the proof.
    4. We will show that P ≠ NP by showing that FACTORING is not in P. SAT might not be a good candidate for separation. This kind of thing has happened before (once): The proof that AC0 ≠ NC1 was done by showing PARITY not in AC0. PARITY is not complete for NC1 under AC0 reduction. The word problem for S5 is, but was not useful for separation. Factoring may be a better candidate for separation since you can generate instances that seem hard, where for SAT this seems hard to do.
    5. Ryan Williams great result shows that there are still things we can do with what we know now. Is P vs NP one of them? NO.
  4. Will the problem still be relevant given advances in SAT solvers? YES. Sat Solvers are GREAT and can solve lots of things- perhaps more than we had thought. But there are still lots that are not. The 17x17 problems has resisted attempts by SAT solvers to solve it (or so I've been told). The problem is a 4-CNF with 4 × 172 vars (not that many), and roughly 4 × 174clauses (too many).
  5. Feel Free to comment on other things:
    1. Graph Isomorphism: We will show P ≠ NP but still not know the status of GI. OR we could find that GI is in P tomorrow.
    2. As noted above, we will show Factoring is NOT in P.
    3. Quantum Computers will never be practical; however, see next note.
    4. Just as the Prob Method is now a STANDARD thing to know even if you are not working on probability, Quantum methods will be a standard thing to know even if you don't work on quantum computing.
    5. We will show L=RL before I do this poll again.
    6. Within 10 years all supermarkets will have self-checkouts that work nicely and that you are expected to use--- except in New Jersey which will outlaw them to create more jobs (as they do now for self-service gas).


  1. Number theoretic problems are much more resıstent to prove lowerbounds than other problems. We don't understand them. We CANNOT even prove their universality for small classes! They have too little simple structure for exploitation. So factoring is not a good candidate to attack. Like other lowerbound the best candidates are combinatorial problems.

  2. "We will show L=RL before I do this poll again."

    Hahaha #1
    Hahaha #2

  3. --- Bulletin of the AMS, April 1, 2013 ---

    Q: Is the PvsNP problem still relevant?

    A: In recent months the mathematics community's appreciation of the PvsNP problem has been substantially augmented by the construction and release under GPL of a class of public key distribution protocols of which only a subset of measure zero can be cracked by that subset of algorithms whose runtimes are provably in P. Formally these key distribution protocols do not separate P from NP; a much-discussed question is whether they separate P from NP sufficiently "for all practical purposes" (FAPP).

  4. If P=NP then comedic possibilities become near-certainties...

    Bulletin of the AMS, April 1, 2020
    On the unexpected efficacy of SAT solvers

    A new generation of SAT-solvers has revealed unexpected structure associated to Intel's hardware random number generators (including both the 80802 Firmware Hub and its successor Bull Mountain): these bitstreams can be emulated by an GNU-standard MT19937 generator ("Mersenne Twister") initialized with seeds found by SAT-solving. Early expectations that this phenomenon might be confined to Intel hardware have been confounded by the surprising discovery — confirmed in recent months by multiple independent laboratories around the world — that data records associated to photon-counting experiments invariably derive from GNU/MT19937 initialized with SAT-guessable seeds. Are we to conclude that the human experience of reality, in its entirety, is a computational simulation? What can we deduce about the algorithms and even the author(s) of the simulation software? And what are the implications (if any) of these experimental findings with respect to PvsNP? This Bulletin of the AMS special issue is devoted to a discussion of these questions, by a panel that includes Lance Fortnow, Bill GASARCH, Dick Lipton, Scott Aaronson, and the Quantum Pontiffs, with moderators David Deutsch, Doron Zeilberger and Richard Stallman.