Computational Complexity

Let R be the set of random strings, the x such that C(x)≥|x|. There are various theorems that many such x must exist at every length. What ...

There is a great Dilbert cartoon explaining the need for Kolmogorov complexity. Because of copyright issues, I won't put it here (but y...

Andrei Kolmogorov was born exactly hundred years ago last Friday the 25th. Kolmogorov made major contributions to "every mathematical ...

Previous CCW Two new complexity classes developed independently for two different purposes with eerily similar definitions. Let's tak...

By request, here is a sketch of the proof of the Berman-Hartmanis 1978 result that all paddable NP-complete sets are isomorphic. The proof ...

As noted in a comment to the last post, it is now official that Ron Rivest, Adi Shamir and Len Adleman won the 2002 Turing Award . Unfort...

The ACM doctoral dissertation award , given to the best doctoral thesis in computer science, was awarded to Venkatesan Guruswami for his...

Often graduate students ask me for a good problem to work on. This is one of the biggest challenges of an advisor. A good problem for a gr...

A couple of interesting pieces in the New York Times. Jim Holt reviews George Johnson's A Shortcut Through Time: The Path to the Q...

In the old commenting system, Daniel Varga had the following comment on my post on unprovability . I guess Alexander Razborov turned t...

Because of the popularity of the war weblogs, the Haloscan commenting system I was using was being overloaded which would on occasion cause...

In the April issue of the Communications of the ACM, Peter Wegner and Dina Goldin have a technical opinion entitled Computation Beyond T...

My post on Fermat's last theorem last week reminded me of my personal all-time favorite math parody, a Chicago Tribune column written ...

"The Institute" in yesterday's post refers to the The Institute for Advanced Study , a fully-endowed facility devoted to funda...

There has been a really amazing development today on Fermat's Last Theorem. Noam Elkies has announced a counterexample, so that FLT is n...

In 1976, Berman and Hartmanis considered whether all of the NP-complete problems might be the same. We says sets A and B are polynomial-ti...

Haipeng Guo asks "Is is possible that the P vs NP problem is undecidable? Is there any paper talking about this?" Short Answer...

Previous Lesson | Next Lesson In the 1950's, Friedberg and Muchnik independently showed that there were sets that were computab...

Some follow-up on earlier posts of this week. The University of Connecticut defeated BYU in men's basketball yesterday, keeping t...

The accepted papers for ICALP have been posted. As I mentioned last week, ICALP has two submission tracks that match the Theory A and The...