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

  • How not to get people to use a new feature

    What I want to do: use my laptop. What I actually end up doing: go digging through the settings to find out why I have a new "Meet Now" icon in the…

  • Audio latency

    Here, have a random scientific paper: The Effects of Latency on Live Sound Monitoring. I keep mentioning this paper to friends and can never find…

  • Of carpentry and networking

    So, I'm not sure if I've bought a wifi router or a Cylon Raider here... Work colleague: Cylon raider. So say we all. Housegroup friend: Or a…

  • 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.