Thursday, January 30, 2014

NP is in DTIME(n^{polylogn})? or not?

While I've been slicing chicken, my phone fetched today's arXiv posts in my topics of interests and I bumped into this. While it's not the "usual" P=NP stuff, I'm still quite sceptical..
..however, if it's correct, that has several serious impacts on complexity theory. And the author has several strong publications..

..worth a read. who knows.
Posted by at

2 comments:

  1. szabivanFebruary 13, 2014 at 10:16 AM

    v2 is out, I wonder what should this imply... ;)

    ReplyDelete
  2. szabivanFebruary 24, 2014 at 9:54 AM

    v3 is out, hm..
    "This paper has been withdrawn due to a fatal flaw in the proof of Lemma 1"
    okay. I've ALMOST started to read it :D

    ReplyDelete

Subscribe to: Post Comments (Atom)