This work is licensed under a
Creative Commons License.
|
Wednesday, January 15, 2003
Supreme Court Rules on InfinityBreaking 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 NSALast 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 ModelI 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: SatisfiabilityPrevious 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 []