## [Computational Complexity] Do we root for how a problem will go?

Expand Messages
• When you are working on a problem do you have a rooting interest in which way it goes? Sometimes yes, sometimes no. A story: A 3-free set is a set with no
Message 1 of 1 , Nov 1, 2007
When you are working on a problem do you have a rooting interest in which way it goes? Sometimes yes, sometimes no. A story:

A 3-free set is a set with no arithmetic progressions of length 3. Large 3-free sets of {1,...,n } were used in the best known Matrix Multiplication algorithm. It is known that there are such sets of size n1-o(1) but there cannot be such sets of size &Omega(n) (slight tighter results are known).

I was finishing up a paper on large 3-free sets. The paper was not about applying these to anything; however, there was a short sections that mentioned some applications. I needed to know, just for some refs and background knowledge, if larger 3-free sets would lead to better Matrix Multiplication algorithms. So I emailed some people involved with Matrix Mult and one of them, Robert Kleinberg, responded. To paraphase the emails back and fourth he said the following (italics are mine):
The known algorithm uses that there are 3-free sets of {1,...,n} of size n{1-o(1)}. Improvements to the current constructions of large 3-free sets will not help matrix mult algorithms. To improve matrix mult algorithms you need sets with more complicated conditions on them. Sorry the answer is not what you wanted it to be
Actually I was happy to know this. I did not really have a rooting interest. Do we root for a result do go a certain way? Do we want to see P=NP (better algorithms) or P\ne NP (better crypto)? (I'd go for better algorithms and let the crypto people find other problems to base systems on- some of which I think has already happened.) Do we want to see P=BPP (confirm our current intuition) or P\ne BPP (confirm our 1980 intuition)? Do we want to see GI\in P or GI \notin P? Do we want to see PH collapse or not collapse? Do we have a rooting interest in any of these problems?

I would think algorithms people root for finding faster algorithms rather than showing a problem is NP complete. Complexity people are happy to either seperate or collapse classes. If only we do it more often.

--
Posted By GASARCH to Computational Complexity at 11/01/2007 12:13:00 PM
Your message has been successfully submitted and would be delivered to recipients shortly.