Computational Complexity


Creative Commons License
This work is licensed under a Creative Commons License.

Powered by Blogger™

Friday, September 12, 2003

Creative Commons

In a conversation I had last week, a professor planned to use slides from lecture notes he found on the web in his own slides. He planned to give attribution to the original producers of the slides but did he need to contact them beforehand for permission. Technically yes, material put on the web is copyrighted by default. But if he sent them email most responses would be of the form, "Please don't waste my time!"

To deal with this issue, Creative Commons has a nice service giving an easy way to release some rights for online material. So I've added a link on the left column of the web log that basically allows you to modify and distribute the material in this weblog for noncommercial use with attribution. No need to ask me, not that anyone has.

On another note, I'm on vacation next week and off the internet. Back after that.

11:02 AM # Comments []  

Thursday, September 11, 2003

Balanced NP Sets

Last week I posed the following question:

(1) Exhibit an NP-complete language L, such that for all lengths n≥1, L contains exactly half (2n-1) of the strings of length n.

This question was posed by Ryan O'Donnell and solved by Boaz Barak. Here is a proof sketch.

By using standard padding and encoding tools, (1) is equivalent to

(2) There is an NP-complete language L and a polynomial-time computable function f such that for every n, there are exactly f(n) strings in L of length n.

First we show how to achieve (2) if we replace "strings" with "total witnesses." Consider pair of formulas φ and ¬φ. The total number of satisfying assignments between them total 2n if the have n variables. We just create an encoding that puts φ and ¬φ at the same length. The total number of witnesses at that length is equal to 2n times the number of formula pairs encoded at that length.

We now prove (2) by creating a language L that encodes the following at the same length for each φ

  1. φ, where φ is satisfiable.
  2. (φ,w) where w is a satisfying assignment for φ and there is another satisfying assignment u<w for φ.
You can check that the language is NP-complete and the total number of strings in L for each φ is just the number of satisfying assignments of φ.

8:06 AM # Comments []  

Tuesday, September 09, 2003

Is P versus NP formally independent?

As promised back in March, the October 2003 BEATCS Complexity Column is on whether we can truly settle the P versus NP question. Scott Aaronson gives quite an interesting survey on this topic.

12:56 PM # Comments []  

Monday, September 08, 2003

STOC 2004

I have received some requests for the call for papers for STOC 2004 which will be held in Chicago. Maybe it is because I gave the presentation for STOC 2004 at the 2003 business meeting, or because if you google 'STOC 2004' this weblog comes up in the list, or just because I'm in Chicago now, but I am not officially connected to STOC 2004.

Having said that, here is the tentative call for papers.

10:50 AM # Comments []