Hacker News new | comments | show | ask | jobs | submit login

I skimmed through the synopsis but this philosophical statement baffles me (although obviously it is unrelated to the validity or invalidity of the proof):

"The implications of [P ?= NP] on the general philosophical question of [..] whether human creativity can be automated, would be profound."

How so? If P!=NP, that is obeyed by the brain as much as by computers and whatever trick our brains does to be creative despite of this, will be available to computers as well, regardless of P?=NP. What am I missing?

You must read it in context.

What it says is that if P == NP then the implications are profound for applications such as cryptography and on the general question of whether human creativity can be automated.

You can see why P == NP would have profound implications for crypto: many of our widely used techniques would turn out to, um, be easy to crack.

I believe the intent regarding human creativity is that humans often end up with a practical need to deal with some real-world instance of a size-able NP-complete problem. We don't know any way to efficiently find the optimal solution so we creatively deal with what we can figure out (the traveling salesman's optimization problem, placed into the real world, might count). Are our creative guessworks and heuristic discoveries essential? Or can automation based on P == NP eliminate the need for them - and do better than we do on these problems.

Lets assume that P==NP, why assume that we would be able to find algorithms to easily crack crypto?

Let me put it another way, lets say that we finally discover that it is possible to time travel to the past. However, the energy needed to travel back int time is the equivalent of a million Suns because that is the amount of energy needed to warp space enough so that time will reverse itself. And we found proof of this when we observed the black holes of two galaxies colliding. So, even if it were possible it would still not matter. Practically speaking, it would still not be possible to travel back in time.

My gut feeling is that if it were to turn out that P==NP that would not necessarily mean that all of a sudden we would be able to find the exact algorithms that make it easy to crack cryptography algorithms easily.

We would know from the proof that such algorithms would exist, and possibly get a method from the proof as to how formulate them.

Also, gut feeling doesn't work in math. I mean, not at all.

NPC algorithms are roughly equivalent, so a P solution to one is a P solution to all. So, assuming the proof would be somewhat constructive, that would give you a P solution.

But, RSA (and probably other) cryptosystems aren't even thought to be NPC to solve... so they're probably unaffected. So, I guess it depends on the implementation details of the cryptosystem. Probably it wouldn't render them wide open, but it might make previously good keys far weaker, and mean that much longer must be spent on encryption for it to be safe (rather than now where a safe key can be decoded almost instantly on an embedded platform).

Polynomial doesn't mean "easy".

O(n^10000) is polynomial but really not easy.

I didn't follow everything in my complexity class, but I believe that P=NP implies that search is as easy as decision. So producing a piece of good music is as easy (up to a polynomial) as deciding if a piece of music is good.

If I remember correctly, optimization also collapses. So finding the best possible piece of music is also easy as deciding if a piece of music is good.

Up to a polynomial.

What if the polynomial is of order 1000 or higher?

I understand asymptotics and the convention that polynomial algorithms are "efficient". However, it might turn out that P=NP but the polynomial is so big that the found algorithm is impractical for normal sized instances.

That's certainly a logical possibility. In practice, low-degree polynomial solutions have been developed for most important problems in P, even if the first known polynomial solution had a high degree.

What would be even more entertaining, is a non-constructive proof of NP=P.

Wikipedia on P ?= NP:

In essence, the question P = NP? asks: if 'yes'-answers to a 'yes'-or-'no'-question can be verified "quickly" can the answers themselves also be computed "quickly"?

Scott Aaronson:

If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss...

The problem with these grandiose statements is that they forget the word formal. You have to be searching on a space that's formally defined to make optimization=verification if P=NP. When we do art and creativity, the space is not formally defined a priori. Hell, even theorem-proving isn't. Look at the breakthroughs in mathematics and most of them, a really large majority, came from applying some new ideas or operations (e.g., ricci flows) to problems that all others simply could not see as applicable. There are no "profound philosophical implications" if P=NP (which I doubt) other than our universe lets us have polynomially bounded algorithms for a huge cluster of problems.

How so? If P!=NP, that is obeyed by the brain as much as by computers and whatever trick our brains does to be creative despite of this, will be available to computers as well, regardless of P?=NP. What am I missing?

Let's talk math: In some very formal, reductionist sense, what we're doing when we do math is to start with a set of axioms, operate on them using a fairly small set of logical rules, and arrive at theorems that seem interesting.

If we do this very carefully -- much more carefully than a human would ever normally do, showing 100% of our work -- it's trivial to check such a proof automatically. You just look at each step, and verify that that step follows from the axioms + logical rules you're using + previous steps. This checking is clearly (handwave) polynomial: at worst, at each step N, you have to examine every axiom, every logical rule, and each prior step to make sure that step N+1 is legal.

So proof checking is in P.

Let's say I have a set of axioms, and a logic, and I want to know whether a theorem T is true given that system. One strategy I could use is to decide to only consider proofs of length less than N, and generate every legal theorem that I can reach in fewer than N logical steps. When I'm done, I check my list of proven theorems and see if any of them match T. Since I can always my answer in polynomial time, I know this is in NP.

The try-everything-possible algorithm has the downside of being a bit exponential (since we expect N to be very (very!) large for any interesting theorem) and so also a bit useless.

But what if a P=NP proof can provide guidance on how we should combine our axioms in order to reach theorem T? We suddenly have not a proof-checker, but a proof-generator! Anything that we can state in a formal language, we can simply ask the prover to prove -- it will either give a proof, or say that a proof of size < N doesn't exist. (That wouldn't be a disproof, and it's a Goedel/halting problem kind of argument that we may never really know how large N needs to be.)

Finding new proofs is a large part of what's considered creative in mathematics. It's hard to over-state how math might change with a tool like that available. The field has seen any number of revolutions before -- e.g., the effort of hundreds who worked on the algebraic roots of polynomials pretty much only survives in homework exercises nowadays -- but automating proofs would be Big.

(Finding interesting conjectures is valuable, too, but I doubt Erdos would be nearly as famous if he'd only posed his questions without his resume of theorems behind them.)

If P != NP, that doesn't mean we will never be able to automate human creativity; it just makes it a bigger challenge.

The general feeling is that creativity is hard, and even exponentially hard. When people try to do things creatively they feel like they aren't doing that much better than trying all possibilities and rejecting the ones that don't work.

If someone proved P=NP then unless we're mistaken about how hard we have to work to think creatively, it's likely that computers will end up being better than us at it, using this algorithm that I suspect would be difficult to backport to our brains. :)

Then again, it's possible that skilled practitioners of any creative field have stumbled across this polynomial time algorithm and don't know it, but that seems unlikely.

In regards to mathematics, creativity is displayed foremost in finding connections between different notions and finding logical arguments to support a claim. Mathematical discovery is not in the claim, but in the construction of the proof of the claim.

Mathematical statements are generally easy to state. If P=NP were true, then a valid proof could automatically and efficiently discovered. This would be a kind of creativity automated by technology.

AFAIK the thinking is that if P=NP then we might be able to automate the creation of theorems because we'd be able to take a problem who's solution is known to be quickly verifiable and because we know it's therefore quickly solvable we might be able to automatically develop the theorem that solves it. So his proof suggests that human creativity can't be automated.

In order to automate human creativity one must understand its nature at least.

I'm not sure why creativity has this special aura. My internal process seems fairly mechanistic, to me.

Perhaps it's a legacy from the idea of a life-force or vis viva.

While I agree P != NP doesn't say anything about human creativity, but the reason it can't be automated is, I think, different: creativity is closely tied to libido and biological evolution, which in turn can't be simulated in machines in full.

I'd argue that if (assuming it's true that) creativity stems from libido and biological evolution, it's been because there are evolutionary gains for creative individuals. The first person to throw a rock at a tree to knock down fruit got more food, for instance. The most complicated clothing (/nest/dance) gets the most mates.

All of which means it's purely a motivating force, not a requirement. We've been motivated to be creative, so we are. Programs can be similarly guided towards ends we desire; perhaps the most direct analogy is genetic programming, where you determine which "breed" by their "fitness" value.

What I actually meant was what we create rather than why.

Exactly my point: what we create is incredibly tightly tied to why we create, especially if you're looking at it from an evolutionary standpoint. I wouldn't call it an isomorphic relationship, but darn close.

You also have to consider that our creativity has been created by the equivalent of billions of the individuals with more computational power than the most powerful computer in the world right now, running for thousands of years of recorded history. Absolutely nothing we have done with computers approaches this, especially when you consider just how unexplored computer A.I. really is. If we call it ten orders of magnitude more "power", we're making a phenomenally conservative estimate. What could you do with a computer over a billion times more powerful than everything that Google owns?

I'd say our less-than-10-billionth computational efforts have in fact created a couple creative things. Which puts them about on par.

"which in turn can't be simulated in machines in full."

If you mean "can never be simulated in machines in full" I would disagree.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact