Tuesday, August 10, 2010

A Different Perspective on P != NP

Ok, obviously this potential proof for P != NP is causing quite a stir. I really wasn't planning on blogging about it, but today I had the opportunity to share the buzz with a group of grade 6-8 girls, so I thought I'd write about it from that perspective, since it's likely nobody else has.

I have a more or less preset workshop design that I use for most of my outreach with girls of this age. I start by introducing myself and explaining how university works before moving into what computer science actually is. I usually let them guess first, then give them a "big fancy definition" from Wikipedia. I break that down into a simple statement: Computer science is about figuring stuff out. This is followed by a list of questions like "What can be figured out automatically?" and "How hard is it to figure out?" I end with a selection of CS Unplugged activities.

I normally use the Travelling Salesman Problem as an example of a problem for the question "How hard is it to figure out?" that seems easy to solve, but that can take a really long time even with modern computers if you give it enough data. The idea that computers can't solve everything blows their minds.

Usually, I leave it at that, but today I threw in a little aside for them. I mentioned that the Travelling Salesman problem was part of a big group of similar problems that take a long time to solve, and that we aren't sure if there's some way to transform them into easier problems. I explained that if we can show how to do that, all these problems we couldn't really solve before suddenly become much easier. That also seemed to blow their mind.

The coolest part? When I mentioned "P vs. NP" some of them actually said "Oooh yeah!" or looked like they had heard the term before. I told them that someone put out a proof in the last couple of days that seems to show that P does not equal NP, and that the whole computer science community has been alight about this. They seemed to like being clued into what was making us all excited these last few days. ;)


Haz said...

Nice to hear ;).

It's hard to convey how exciting it is to hear Steve Cook say anything positive about one of these proofs -- rumour has it that he gives the approach a 1% chance of success (unbelievably high, all things considered).

It'd be a very different world for those girls if this paper pans out...

Gail Carmichael said...

So true... we'll all be watching and waiting!

Post a Comment

Comments are moderated - please be patient while I approve yours.