Practically P=NP?

Gödel's Lost Letter and P=NP


Boris Konev and Alexei Lisitsa are both researchers at the University of Liverpool, who work in Logic and Computation. They have recently made important progress on the Erd?s Discrepancy Problem using computer tools from logic. Unlike the approach of a PolyMath project on the problem, their proof comes from a single program that ran for just over 6 hours, a program administered only by them, but mostly not written by them.

Today Ken and I wish to talk about their paper and two consequences of it.

Their paper can be read at two levels. On the surface the paper is about the famous discrepancy conjecture of Paul Erd?s, which we have talked about before. I will state the precise conjecture in a moment, it was said that previously the best lower bound for a certain “constant” was 1 and they moved it to 2. Since Erd?s conjectured that…

View original post 1,694 more words

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s