Friday, September 12, 2003
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
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.
Thursday, September 11, 2003
Balanced NP Sets
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
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 φ
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 φ.
- φ, where φ is satisfiable.
- (φ,w) where w is a satisfying assignment for φ and there is
another satisfying assignment u<w for φ.
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.
Monday, September 08, 2003
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.