A Serious Clown

Ramblings of a lackadaisical

Archive for August 2014

A Class of Graph Properties Computable in Linear Time

leave a comment »

A cool theorem.

Gödel's Lost Letter and P=NP

Ron Fagin is a great theorist who has made many important contributions to diverse aspects of computing. He is perhaps most famous for his brilliant categorization of polynomial time by second order logic—Fagin’s Theorem.

Today I plan on talking about a related theorem—Courcelle’s—proved in 1990. Yet the theorem is not, in my opinion, as well known as it should be. The truth is I did not know this pretty theorem until I ran across it the other day. So perhaps everyone else knows Courcelle’s result except for me. Oh well.

View original post 940 more words


Written by Spike Spiegel

August 28, 2014 at 6:34 pm

Posted in Uncategorized