Complexity Theory

———————
From Scott Aaronson (draft for SciAm article March 2008):
A second answer comes from a 1975 theorem of Theodore Baker, John Gill, and Robert Solovay, who showed that “diagonalization — the technique used by Gödel and Turing to prove their incompleteness and undecidability theorems” is not strong enough by itself to separate P from NP. A third answer has to do with the bizarre self-referential nature of P?NP, a conjecture that all but asserts the difficulty of finding its own proof. In 1993, Steven Rudich and Alexander Razborov showed that most of the approaches then being tried on P?NP and related conjectures would, if they worked, yield efficient algorithms to solve some of the very problems that they were supposed to prove intractable!

Language Theory (Wed Apr 16 16:42:03 PDT 2008)

——————-
Investigate partial ordering in directed cyclic and how it might still be possible to have inheritance in presence of a cycle. Look for a way to extend python2.3’s method resolution order. Also, make a relevant post about how the inherent linearity of written (and spoken) language (conventional left-right order) affects the design of an mro in cyclic graphs.

Make remarks about Library Science and Information Retrieval (Wed Apr 16 16:42:03 PDT 2008)

——————-
must categorize all my downloads (Books, movies, music, misc)
use of thesaurus as distance (think Levenstein) metric for word association in search.
People usually use very few search terms, would be nice if engine could take from that and search the related words.
Look at word clusterings, that is for any two words in english, the thesaurus should show a nice ring of other words that are related to the first two. This ring can be weighted according to graph distance. Focus on results that also have words in the denser parts of that ring.

Write a post about:

——————-

• The misnomer of Computer Science as a field.
• reverse Wavelets: given a set of data, reverse engineer the basis wavelet that leads to optimal compression.