### Wednesday, January 15, 2003

**Supreme Court Rules on Infinity**

Breaking news on a post from last October. The
US Supreme Court ruled in favor of Disney that ever increasingly long
finite lengths of copyright protection does not violate the constitutional prohibition against indefinite copyrights.
10:25 AM
#
Comments
[]

**Our Friends at the NSA**

Last weekend the movie *Enemy of the State* was
shown on network television in the US. This is a pretty good thriller
about a rogue NSA official using the resources of the NSA to get back
some evidence from a lawyer innocently tangled up in this affair.
What do we know about the National
Security Agency? While they don't have the best American
mathematicians, who typically go to universities, they have a large
collection of very good mathematicians. While they are free to read
the same papers I read, we hear about very little of their work. They
must have some exciting work in algorithms and complexity I can only
dream about. Perhaps they have an efficient factoring algorithm or a
working quantum computer in their basement. Unlikely, but possible.

Occasionally I meet NSA scientists at conferences, particularly those
meetings devoted to quantum computation. "The NSA is much more
interested in quantum computing than quantum cryptography," one
such scientist told me. This surprised me since quantum cryptography
seems much more likely to have real-world applications than quantum
computers, both in theory and in practice. "The real issue is how
long our current codes will remain unbreakable. We need to know if our
the information currently encrypted will remain safe for 20 or 50
years."

So is *Enemy of the State* realistic? "Not at all," a
different NSA employee told me at a quantum workshop shortly after the
movie came out. "We work in boring cubicles, not the sleek
offices depicted in the movie." Offices?! What about the satellites
that can track people on the ground in real time? "No comment."

6:01 AM
#
Comments
[]

### Monday, January 13, 2003

**A Physics-Free Introduction to the Quantum Computation Model**

I just posted to the BEATCS Complexity Column Web Page the February column, written by Steve Fenner, that gives an overview
of quantum computing to those of us without a physics background.
Do you have a survey that you are dying to write? I am always looking for volunteers for the column.

2:06 PM
#
Comments
[]

### Sunday, January 12, 2003

**Foundations of Complexity **

Lesson 13: Satisfiability

Previous Lesson |
Next Lesson
Boolean-Formula Satisfiability (SAT) is the single most important
language in computational complexity. Here is an example of a Boolean
formula.

(u OR v) AND (u OR v)
u and v are variables that take on values from {TRUE, FALSE}. u means the negation of u. A *literal* is either
a variable or its negation.

An *assignment* is a setting of the variables to true and false, for
example (u→TRUE, v→FALSE). Once all of the variables are
assigned a truth value, the formula itself has a truth value. The
assignment (u→TRUE, v→FALSE) makes the formula above
false. A *satisfying assignment* is an assignment that makes the formula
true. For the formula above, the assignment (u→TRUE, v→TRUE)
is satisfying. If a formula has a satisfying assignment we say the
formula is *satisfiable*.

SAT is the set of satisfiable formula. The formula above is in
SAT. This formula is not.

u AND (u OR v) AND (u or v)
A formula is in conjunctive normal
form (CNF) if it is the AND of several clauses, each consisting of an
OR of literals, like the formulas above. A disjunctive normal form
(DNF) formula is the same with AND and OR reversed. A formula is
k-CNF if every clause has exactly k literals. The first formula
above is in 2-CNF.

CNF-SAT is the set of satisfiable CNF formulas. k-CNF-SAT or k-SAT is
the set of satisfiable formulas in k-CNF.

Cook and Levin independently showed that SAT is NP-complete.
The problem remains NP-complete if we restrict to CNF-SAT or even
3-SAT.

Next lesson we will show that CNF-SAT is NP-complete.

8:44 AM
#
Comments
[]