Programs that run all small programs in parallel and pick the winner: blog.computationalcomplexity.o

This idea gives the long-known but counterintuitive result that there is an already-known algorithm that, if P=NP, solves all solvable instances of satisfiability in polynomial time. Gasarch gives a nice roundup of explanatory links in this new blog post.

Sign in to participate in the conversation

A Mastodon instance for maths people. The kind of people who make \(\pi z^2 \times a\) jokes.

Use \( and \) for inline LaTeX, and \[ and \] for display mode.