Friday, March 28, 2003

The Berman-Hartmanis Isomorphism Conjecture

›
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-ti...
1 comment:
Thursday, March 27, 2003

Is P versus NP undecidable?

›
Haipeng Guo asks "Is is possible that the P vs NP problem is undecidable? Is there any paper talking about this?" Short Answer...
Monday, March 24, 2003

Foundations of Complexity
Lesson 16: Ladner's Theorem

›
Previous Lesson | Next Lesson In the 1950's, Friedberg and Muchnik independently showed that there were sets that were computab...
7 comments:
Friday, March 21, 2003

On Basketball and Politics

›
Some follow-up on earlier posts of this week. The University of Connecticut defeated BYU in men's basketball yesterday, keeping t...
Thursday, March 20, 2003

ICALP Papers Announced

›
The accepted papers for ICALP have been posted. As I mentioned last week, ICALP has two submission tracks that match the Theory A and The...
Wednesday, March 19, 2003

Information Markets

›
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, ...
Tuesday, March 18, 2003

It's Not a Tree After All

›
On Sunday, I posted a link to the 2003 NCAA Division 1 Men's Basketball Championship Brackets which I called "America's Favo...
Monday, March 17, 2003

War and This Weblog

›
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 gov...
Sunday, March 16, 2003

March Madness

›
Check out America's Favorite Binary Tree .
Friday, March 14, 2003

Doing homework the hard way

›
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 ev...
Thursday, March 13, 2003

Complexity Class of the Week: The Permanent

›
Previous CCW Let A={a ij } be an n×n matrix over the integers. The determinant of the A is defined as Det(A)=Σ σ (-1) |σ| a 1σ(1) a...
Tuesday, March 11, 2003

Theory A and Theory B

›
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 wa...
Monday, March 10, 2003

Talk Posted

›
I posted the slides of my talk, "Church, Kolmogorov and von Neumann: Their Legacy Lives in Complexity" that I presented at the Du...
Tuesday, March 04, 2003

Rush Hour

›
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 ...
Saturday, March 01, 2003

Cardinality Theorem for Regular Languages?

›
Till Tantau told me an interesting open question at STACS. Kummer proved the following Cardinality Theorem for the recursive sets: Fix a con...
Friday, February 28, 2003

Howdy from Berlin

›
I'm writing from the STACS conference, one of my favorite European conferences. Next week I'll be in Holland visiting CWI and tal...
Tuesday, February 25, 2003

A Zero-One Law for RP

›
Russell Impagliazzo and Phillipe Moser have an upcoming Complexity paper entitled A Zero-One Law for RP . What does that mean? Jack Lut...
Monday, February 24, 2003

Complexity Papers Announced

›
The list of accepted papers for the 18th Annual IEEE Conference on Computational Complexity is now available. The conference will be ...
Friday, February 21, 2003

More on Perfect Graphs

›
Today I saw Maria Chudnovsky give a talk at Princeton on her new result with Paul Seymour finding a polynomial-time algorithm for testing p...
Monday, February 17, 2003

Complexity Class of the Week: BPPpath

›
Previous CCW Let us call a nondeterministic Turing machine M balanced if for every input x, all of its computational paths have the sa...
4 comments: