Thursday, October 15, 2009

Thanks for the Fuzzy Memories

In the 1990's Manindra Agrawal and V. Arvind published a paper claiming that if SAT is reducible to a (non-uniform) weighted threshold function then P = NP. Their proof relied on the following splitting lemma:

For all n, and qij∈{0,1}n, 1 ≤ i ≤ j ≤ n+2, there don't exist dk∈{0,1}n, 1 ≤ k ≤ n+2 such that for all i,j, and k, dk⋅qij > 0 if k=i or k=j and dk⋅qij < 0 otherwise.

Manindra Agrawal and Thomas Thierauf used the splitting lemma to give a polynomial-time algorithm for factoring. They got quite excited and couldn't find a bug in their proof. Apparently I suggested to Thomas at the time that he patent the algorithm before they publish. But later Klaus Wagner showed the splitting lemma actually implied P=NP and Agrawal went back and found that the proof of the splitting lemma wasn't correct and Jochen Messner found a counterexample.

Manindra wrote a retraction for Theoretical Computer Science but for some reason it wasn't published.

I've seen this before. If a technical lemma doesn't imply anything particularly surprising, it might not get checked very carefully. But only later when researchers start using it to get amazing results do people go back and realize there was a problem with the lemma after all.

Flash forward more than a decade later to this week at Dagstuhl. Harry Buhrman, John Hitchcock and Harry's student Bruno Loff came to Dagstuhl all excited. They proved that SAT disjunctively-tt reducible to a sparse set implies SAT is reducible to a weighted threshold and by Agrawal-Arvind thus implies P = NP, answering a long-standing open question. We tried to understand the Agrawal-Arvind paper and Thomas Thierauf "vaguely remembered" there might have been a bug in the splitting lemma.

Arvind who is here at Dagstuhl didn't remember the paper well. Manindra, one of the organizers of this week's workshop, is not here at all but had to attend an IIT event in of all places Chicago. Eventually Harry called Manindra who acknowledged the bug.

Once revealed Jacobo Torán, Messner's advisor, told me the whole sordid story above and Nikolai Vereshchagin showed the splitting lemma true for n ≤ 4 and found counterexamples for n ≥ 5. After talking about the conjecture at the open problem session last night, at breakfast Amir Shpilka showed me an easy proof that the splitting lemma fails even if you allow an infinite number of points for n = 5.

Don't worry, Manindra's proof with Kayal and Saxena that Primes are in P is still safe.

11 comments:

  1. I don't understand why there isn't more pressure on the authors to get their retraction published. Their failure to follow up has now wasted lots of people's time.

    ReplyDelete
  2. Can the theorem be recovered nevertheless? I.e. does SAT reducible to a weighted threshold function imply P=NP?

    ReplyDelete
    Replies
    1. Adding this note here in case anyone come across this in the future. A few years after this post, in MFCS '13 Buhrman, Fortnow, Hitchcock, and Loff (https://doi.org/10.1007/978-3-642-40313-2_23) proved that if SAT is reducible to a weighted threshold function then PH=P^NP. So, not quite as good as concluding P=NP, but at least still shows that PH would collapse.

      Delete
  3. Is there a typo? It says "d_k⋅q_ij < 0", but both are bit strings.

    ReplyDelete
  4. Wim, just think of them as 0-1 vectors.

    ReplyDelete
  5. Don't worry, Manindra's proof with Kayal and Saxena that Primes are in P is still safe.

    This last bit is absolutely uncalled for. Mistakes can and does happen to everyone. Anyone who claims otherwise is either lying or does not do research.

    Just to cite a famous example, it took Poincare several papers to formulate the so called Poincare conjecture -- all of which (along with his other papers on algebraic topology) were erroneous.
    See Dieudonne's beautiful exposition of Poincare's work in his "History of Algebraic and Differential Topology". Nevertheless, Poincare is accepted as the founder of the field of algebraic topology.

    ReplyDelete
  6. Last anonymous: I don't think the comment was "uncalled for", but, despite probably being true, I imagine it was a bit tongue-in-cheek.

    I think that the AKS Primes in P result has been: a) read thoroughly by enough people b) extended by enough people c) taught by enough people and d) is simple enough that at this point it is very unlikely to contain errors.

    (This probably happens with many popular results whose proofs are not particularly hairy.)

    --Anon. 3

    ReplyDelete
  7. The original problem that I heard from Lance was for arbitrary vectors in R^n, not {0,1}^n. It does seem hard to get a negative dot product from two 0-1 vectors :)

    ReplyDelete
  8. CI fellows finally announced on cifellows.org

    ReplyDelete
  9. This probably is an out-of-context question but what is your opinion about the correctness/validity of Schnorr's polynomial time factoring algorithm published recently.

    ReplyDelete
  10. What is the largest number that Schnorr factored with his method? 15? That might answer your question.

    ReplyDelete