Prevous Lesson We will show that CNF-SAT is NP-complete . Let A be a language in NP accepted by a nondeterministic Turing machine M. Fix an input x. We will...
4
Lance Fortnow
fortnow
Jan 21, 2003 5:08 pm
Last night I (and forty other complexity theorists) received by email an anonymous paper entitled "NP = coNP". After a quick scan it was clear there was not...
5
Lance Fortnow
fortnow
Jan 23, 2003 12:24 pm
Just in case you thought computer scientists only deal with computers, here is a New York Times article describing how AT&T researcher Matt Blaze using tools...
6
Lance Fortnow
fortnow
Jan 23, 2003 4:32 pm
One cannot celebrate Alonzo Church, part of our Celebration of Geniuses without talking about his creation, the Lambda Calculus, a way to describe functions...
7
Lance Fortnow
fortnow
Jan 24, 2003 4:25 pm
Last year we saw the resolution of the Strong Perfect Graph Conjecture, a major result in graph theory . The conjecture stated that a graph is perfect if and...
8
Lance Fortnow
fortnow
Jan 24, 2003 7:21 pm
Next week I will go away on vacation. When I go on a real vacation I go cold turkey on the Internet. No new posts or responses to comments or email until I...
9
Lance Fortnow
fortnow
Feb 3, 2003 5:34 pm
The list of accepted papers of STOC has been posted. STOC and FOCS are the two most important annual theoretical computer science conferences. Quite a few...
10
Lance Fortnow
fortnow
Feb 5, 2003 10:18 pm
For those with access to the Journal of the ACM , the fiftieth anniversary issue (Volume 50, Number 1) has a number of very short articles by prominent...
11
Lance Fortnow
fortnow
Feb 11, 2003 10:04 pm
Daniel Varga asks about the question of NEXP not in P/poly and whether it is "fundamentally" easier than NP not in P/poly. As a reminder: NEXP is the class of...
12
Lance Fortnow
fortnow
Feb 13, 2003 3:53 pm
Previous Lesson Now that we have shown that CNF-SAT is NP-complete we can use it to show many other problems are NP-complete via the following lemma. Lemma: If...
13
Lance Fortnow
fortnow
Feb 14, 2003 4:01 pm
Yesterday's post on NP-complete problems reminds me of one of the more interesting open questions, the complexity of the traveling salesman problem on the ...
14
Lance Fortnow
fortnow
Feb 16, 2003 4:14 pm
I noticed that Slashdot has recently mentioned some TCS research. This would therefore be theoretical computer science that matters to nerds. The first was a...
15
Lance Fortnow
fortnow
Feb 17, 2003 4:05 pm
Previous CCW Let us call a nondeterministic Turing machine M balanced if for every input x, all of its computational paths have the same length, i.e., the...
16
Lance Fortnow
fortnow
Feb 21, 2003 7:15 pm
Today I saw Maria Chudnovsky give a talk at Princeton on her new result with Paul Seymour finding a polynomial-time algorithm for testing perfect graphs, a...
17
Lance Fortnow
fortnow
Feb 24, 2003 7:06 pm
The list of accepted papers for the 18th Annual IEEE Conference on Computational Complexity is now available. The conference will be held July 7-10 in rhus,...
18
Lance Fortnow
fortnow
Feb 25, 2003 8:51 pm
Russell Impagliazzo and Phillipe Moser have an upcoming Complexity paper entitled A Zero-One Law for RP . What does that mean? Jack Lutz defined a notion of...
19
Lance Fortnow
fortnow
Mar 4, 2003 9:43 am
John Tromp at CWI has been telling me about some work he is doing on the Rush Hour problem. Rush Hour is a puzzle where you have to remove a car stuck in...
20
Lance Fortnow
fortnow
Mar 10, 2003 9:24 pm
I posted the slides of my talk, "Church, Kolmogorov and von Neumann: Their Legacy Lives in Complexity" that I presented at the Dutch Theory Day last week, for...
21
Lance Fortnow
fortnow
Mar 11, 2003 6:48 pm
Four speakers are chosen for the NVTI Theory Day along two axis: In and out of the Netherlands, and Theory A and Theory B. For example I was the non-Dutch...
22
Lance Fortnow
fortnow
Mar 13, 2003 7:52 pm
Previous CCW Let A={a ij } be an nn matrix over the integers. The determinant of the A is defined as Det(A)= (-1) || a 1(1) a 2(2) ...a n(n) where ranges over...
23
Lance Fortnow
fortnow
Mar 14, 2003 1:27 pm
In yesterday's post I linked to some lecture notes of Vigoda on Valiant's result. Those notes also cite a paper of Zank. Now every paper has a story but this...
24
Lance Fortnow
fortnow
Mar 17, 2003 1:00 am
Check out America's Favorite Binary Tree . -- Posted by Lance Fortnow to My Computational Complexity Web Log at 3/16/2003 7:59:43 PM Powered by Blogger Pro...
25
Lance Fortnow
fortnow
Mar 17, 2003 3:54 pm
I was teaching my class right after the first Gulf war started in 1991 and wondering what to say. Sometimes I wish I were a history or government professor and...
26
Lance Fortnow
fortnow
Mar 18, 2003 2:56 pm
On Sunday, I posted a link to the 2003 NCAA Division 1 Men's Basketball Championship Brackets which I called "America's Favorite Binary Tree". But in a strange...
27
Lance Fortnow
fortnow
Mar 19, 2003 3:06 pm
Suppose you want to make a prediction on say who will win the Best Actress Award at Sunday's Oscars. You can visit various web sites, look at the predictions...
28
Lance Fortnow
fortnow
Mar 20, 2003 11:56 am
The accepted papers for ICALP have been posted. As I mentioned last week, ICALP has two submission tracks that match the Theory A and Theory B split. The list...
29
Lance Fortnow
fortnow
Mar 21, 2003 7:25 pm
Some follow up on earlier posts of this week. The University of Connecticut defeated BYU in men's basketball yesterday, keeping the integrity of the tree . If...
30
Lance Fortnow
fortnow
Mar 24, 2003 10:29 pm
Previous Lesson In the 1950's, Friedberg and Muchnik independently showed that there were sets that were computably enumerable, not computable and not ...
31
Lance Fortnow
fortnow
Mar 27, 2003 12:27 pm
Haipeng Guo asks "Is is possible that the P vs NP problem is undecidable? Is there any paper talking about this?" Short Answer: Until we have a proof that PNP...
32
Lance Fortnow
fortnow
Mar 28, 2003 3:41 pm
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-time isomorphic if...
