## [Computational Complexity] The Kakeya Conjecture over finite fields resolved!...

Expand Messages
• Recently the Kakeya Conjecture over finite fields (henceforth Kakeya) was resolved. For information on what Kakeya is and how it was solved see Dvir s paper On
Message 1 of 1 , Nov 12 8:07 AM
• 0 Attachment
Recently the Kakeya Conjecture over finite fields (henceforth Kakeya) was resolved. For information on what Kakeya is and how it was solved see Dvir's paper On the size of Kakey Sets over Finite Fields that solved it or a nice entry on Terry Tao's blog. Some Applications of the techniques are in the paper by Dvir and Wigderson Kakeya Sets, new mergers and old extractors.

Fields Medal Winner Terry Tao and others worked on Kakeya. There were partial results with difficult proofs. But the final proof was easy to understand. This does NOT mean it was easy to generate- we all suspect verifying is easier than generation. How easy was the proof to understand? So easy that I saw and understood a talk on it in seminar and was able to reconstruct it while proctoring an exam.

Whenever I see a math problem solved in a way that is easy but had been missed I wonder: is there an easy solution to P vs NP that is eluding us?
1. Kakeya did not have a community of people working on it. Even though the people working on it were brilliant there were not that many of them. To solve a math problem may require a diversity of viewpoints. P vs NP has alot of people interested in it. Are they working on it? Do they have a diversity of viewpoints? I honestly don't know.
2. There had been partial results on Kakeya. Hence there was hope. At this time there has been very little progress on P vs NP. (I would welcome counterarguments to this.)
3. There were no results saying such-and-such technique cannot be used to solve Kakeya. For P vs NP there are several such results: oracles, natural proofs, algebraization. (hmmm- is having three results really having several results?). Is P vs NP the only currently open problem in math where there has been considerable effort in showing what techniques won't work? There may be some others in set theory where the conclusion Ind of ZFC is a real option, but how about in fields of math where we expect to get a real answer?
4. If P=NP (which I doubt) then a simple-to-follow-but-quite-clever proof that eluded us all is plausible. If P\ne NP then I doubt this would happen.

--
Posted By GASARCH to Computational Complexity at 11/12/2008 10:05:00 AM
Your message has been successfully submitted and would be delivered to recipients shortly.