Thomas (boggyb) wrote,

  • Mood:

P ≠ NP and Martian teapots

This took a little longer to write than I was hoping for. I did at least start typing before midnight...

While chatting with elemnar earlier we ended up discussing P versus NP (not quite sure how we ended up on that topic), and she came up with a surprisingly good analogy for it: proving P ≠ NP is like proving that there are no teapots orbiting Mars.

In a nutshell, P versus NP is about splitting problems in Computer Science into Easy and Hard problems. Problems in class P are Easy to solve, while problems in class NP are Hard to solve. Except we don't know for certain that NP problems are Hard because no-one's managed to come up with a proof for this. The best we've got is that we've only been able to find Hard algorithms for NP problems.

Note that this is very oversimplified. Some Hard problems are quite quick to solve in practice. Some Easy problems take ages to solve. Some Hard problems can be done in an Easy way to give a "good enough" answer for most purposes. But in general, Hard problems take longer than Easy problems and the difference becomes more significant as the problem becomes larger.

The general thinking in Computer Science is that P ≠ NP, i.e. there is a class of problems that will always be inherently Hard to solve. Indeed a large chunk of modern computing relies on this assumption.

Anyway, what has this got to do with teapots and Mars? Well, how do you know there isn't a teapot orbiting Mars? There aren't any giant teapots as someone would have spotted them by now, but all that gives is an upper bound on the potential size of any teapots (similar to how we've found various algorithms for NP problems and so have an upper bound on how Hard they are). No-one's come up with a formal proof for a presence or absence of a teapot, similar to how there's no formal proof either way for P versus NP. So all we know is no-one's seen a teapot, and there probably isn't one because it all makes much more sense that way... but there could be one out there somewhere that we've just not found yet. And P = NP might be true after all.

Poll #2074983 P ≠ NP and Martian teapots

Are Hard problems Easy?

P ≠ NP (Hard problems are Hard)
P = NP (Hard problems are Easy)

Is there a teapot orbiting Mars?

There is tea on Mars!
The teapot is a lie!

All polls need a ticky box

Ticky box!
Tags: computing, science

  • Poor snowpeople

    Alas, the snow was not to last...

  • The snowmen

    The housegroup WhatsApp was full of people building snowmen (not to mention my FB feed), and it occurred to me that I had a balcony load of pristine…

  • The sky has fallen!

    Work is having a snow day - the boss texted yesterday evening to say "it's pretty tricky on the roads around there so don't try to come to work in…

  • Post a new comment


    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.