News on Intermediate Problems

Gödel's Lost Letter and P=NP

EricDasRyanCody

Eric Allender, Bireswar Das, Cody Murray, and Ryan Williams have proved new results about problems in the range between $latex {mathsf{P}}&fg=000000$ and $latex {mathsf{NP}}&fg=000000$-complete. According to the wide majority view of complexity the range is vast, but it is populated by scant few natural computational problems. Only Factoring, Discrete Logarithm, Graph Isomorphism (GI), and the Minimum Circuit Size Problem (MCSP) regularly get prominent mention. There are related problems like group isomorphism and others in subjects such as lattice-based cryptosystems. We covered many of them some years back.

Today we are delighted to report recent progress on these problems.

View original post 1,603 more words

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s