Re: Can humans solve np-complete problems?

Question: Can humans solve np-complete problems? From: Peter Gadzinski Grade: grad (science)

It is safe to assumed that the human brain can solve complex problems (like pattern and voice recognition and path navigation) that computers currently can't. The question is, has anyone actually done the formal proof that the human brain can actually solve an NP-complete problem? That is, has anyone ever formalized a problem that humans can solve, and prove that humans can solve it exactly (and not just heuristically)? An example is chess : except for errors due to fatigue, humans can out-perform computers. Given the number of brain cells and time and level of solution, however, is this proof of an human-brain polynomial solution of an NP-complete problem?

A problem is in NP (which stands for Nondeterministic Turing machine Polynomial time solvable) if an answer to the problem can be checked in polynomial time by a Turing machine. An example of a problem in NP is factoring: if you successfully factor a number, the answer can be quickly checked by multiplication. A Turing machine is a very specific model of computing that involves a read-write head and an infinite length sequential tape. It has a very precise definition.

A problem is NP-complete if an algorithm for solving the problem in polynomial time can be used to solve any problem in NP in polynomial time. Examples include such mind twisters as the 3-colorability problem and the ever popular Traveling Salesman Problem.

The point is that to say that a problem is in NP or is NP-complete implies that we are using a particular well defined model of computation: the Turing machine. With humans, we do not have a well defined model of how our brains compute. In fact, I was just on the Ph.D. committee of a student whose entire thesis was examining one particular method of how auditory neurons might work. The brain as a whole is far more complex. While neurophysiology has made leaps and bounds in the past few decades, it is fair to say that no general computational model of the brain exists. (That includes neural nets, which although inspired by studies of biological systems are not considered a true model for how the brain works.)

Without such a model, there cannot be a mathematical proof that the human brain can or cannot solve NP-complete problems in polynomial time. The model is key, which is why Turing machines are still studied as a theoretical construct even though they are entirely unpractical as a real computing machine.

As a final note, I would not use chess as an example of human computing superiority. Ever since Deep Blue defeated Kasparov in 1997 human dominance in chess has been shaky. Given the steady advances in computing power in the last six years (Moore's Law at work), today a program of Deep Blue's caliber fits on a laptop. In a match played this year against one such program, Deep Junior, Kasparov went 1 win, 1 loss and 4 draws. Soon even the excuse of fatigue will fall flat. Today most chess computers are consigned to playing against one another to determine their rankings.