Skip navigation

29 May 2012

I’d like to talk about Computational Complexity, in particular, aspects of P = NP. And how we as a society inconsistently apply its consequences. To ground the concept of P and NP, Scott Aaronson gives the example that if P (the algorithms whose work grow reasonably – say polynomially – with respect to input size) and NP (those that don’t but whose results can be easily verified) were equal then composing like Bach would be just as easy as listening to his work and creating beautiful art and poems would be just as easy as seeing/reading them. That proving would be just as easy as verifying a proof and writing as easy as reading. In short, roughly, if P = NP then producing should be just as easy as consuming. This is a good sign that P ≠ NP.

But the intricacies of P = NP is not what I want to talk about, I only wanted to set the stage for my real point. I want to observe how in daily talking, we make statements that imply P = NP. Consider the following two set of statements:

“In 2002 scientist X won the Nobel prize for making bacteria glow in the dark. Today high school students can do it”. Or “it took hundreds of years of work by the most brilliant minds to devise algebra and calculus but today we teach it to high schoolers”.

Also observe statements like: “mining asteroids in space will never be profitable, it would cost trillions just to get there and back”. Or “that energy source/technology will never work, we spend many billions a year just to get back a net negative”.

The first class of statements are meant to impress you with how far we’ve come. What is interesting about these statements is if you look closely they are making the mistake of assuming P = NP. That verifying/making use of a solution is as hard as finding it. It’s true high schoolers can now make art with bacteria but that doesn’t mean we are getting exponentially better at doing arbitrary hard things. This conflates our capabilities (improving exponentially) with the amount of time it takes to solve hard problems (not uniformly improving exponentially). That is, if humanity were some kind of giant computer, they would be growing exponentially in memory and speed but still could not solve problems that grow exponentially with complexity in a reasonable amount of time (assuming P ≠ NP). Except when we can exploit regularities.

We can only exploit more structure due to an increased knowledge base and resources due to more people and better computational abilities but as any Automated Theorem prover will tell you, this is because we don’t need to derive completely from scratch every time we wanted to add two numbers. The amount of time can only make use of exponentially improving capabilities if it can be shown to have a link in common with our existing knowledgebase. Until this link is known we won’t know how long something will take to solve. But it’s worth noting that expanding capabilities increases the probability of finding such bridges, so we are improving our ability to solve problems, just not arbitrarily exponentially.

The second class of statements make the mistake in the opposite direction. They are meant to impress you with how hard trying things are – which is true – but consuming the results is far easier. Building the first ship, set of robots for mining and the infrastructure for their support will cost many multiples of billions. But only the first mission. Consider that each time we do algebra we don’t need to derive and prove the whole subject from scratch. We use the scaffolding and results from earlier to make things much cheaper and easier. We then use it to prove even more difficult things. This is something that needs to be drilled into people who think they are being practical by pointing out how expensive a new endeavor will be. Trivially true but the increased capability will easily replace the costs in ways we can’t imagine.

I’ve never seen the first argument made before and while the second is common, I’ve never seen an analogy to P and NP used to shed light on how silly it is to make statements of why something shouldn’t be done because of how expensive it will be. Producing results is harder than consuming their consequences, unless P = NP.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: