?

Log in

No account? Create an account
P ≠ NP and Martian teapots - 'Twas brillig, and the slithy toves did gyre and gimble in the wabe [entries|archive|friends|userinfo]
Thomas

[ website | Beware the Jabberwock... ]
[ deviantArt | the-boggyb ]
[ FanFiction | Torkell ]
[ Tumblr | torkellr ]

Links
[Random links| BBC news | Vulture Central | Slashdot | Dangerous Prototypes | LWN | Raspberry Pi]
[Fellow blogs| a Half Empty Glass | the Broken Cube | The Music Jungle | Please remove your feet | A letter from home]
[Other haunts| Un4seen Developments | Jazz 2 Online | EmuTalk.net | Feng's shui]

P ≠ NP and Martian teapots [Thursday 16th November 2017 at 11:58 pm]
Thomas

boggyb
[Tags|, ]
[Feeling |sillysilly]

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)
3(100.0%)
P = NP (Hard problems are Easy)
0(0.0%)

Is there a teapot orbiting Mars?

There is tea on Mars!
1(33.3%)
The teapot is a lie!
2(66.7%)

All polls need a ticky box

Ticky box!
3(100.0%)
Link | Previous Entry | Share | Next Entry[ Penny for your thoughts? ]