63
$\begingroup$

This question is something I've wondered about for a while.

When people describe the P vs. NP problem, they often compare the class NP to creativity. They note that composing a Mozart-quality symphony (analogous to an NP task) seems much harder than verifying that an already-composed symphony is Mozart-quality (which is analogous to a P task).

But is NP really the "creativity class?" Aren't there plenty of other candidates? There's an old saying: "A poem is never finished, only abandoned." I'm no poet, but to me, this is reminiscent of the idea of something for which there is no definite right answer that can be verified quickly...it reminds me more of coNP and problems such as TAUTOLOGY than NP or SAT. I guess what I'm getting at is that it's easy to verify when a poem is "wrong" and needs to be improved, but difficult to verify when a poem is "correct" or "finished."

Indeed, NP reminds me more of logic and left-brained thinking than creativity. Proofs, engineering problems, Sudoku puzzles, and other stereotypically "left-brained problems" are more NP and easy to verify from a quality standpoint than than poetry or music.

So, my question is: Which complexity class most precisely captures the totality of what human beings can accomplish with their minds? I've always wondered idly (and without any scientific evidence to support my speculation) if perhaps the left-brain isn't an approximate SAT-solver, and the right-brain isn't an approximate TAUTOLOGY-solver. Perhaps the mind is set up to solve PH problems...or perhaps it can even solve PSPACE problems.

I've offered my thoughts above; I'm curious as to whether anyone can offer any better insights into this. To state my question succinctly: I am asking which complexity class should be associated with what the human mind can accomplish, and for evidence or an argument supporting your viewpoint. Or, if my qusetion is ill-posed and it doesn't make sense to compare humans and complexity classes, why is this the case?

Thanks.

Update: I've left everything but the title intact above, but here's the question that I really meant to ask: Which complexity class is associated with what the human mind can accomplish quickly? What is "polynomial human time," if you will? Obviously, a human can simulate a Turing machine given infinite time and resources.

I suspect that the answer is either PH or PSPACE, but I can't really articulate an intelligent, coherent argument for why this is the case.

Note also: I am mainly interested in what humans can approximate or "do most of the time." Obviously, no human can solve hard instances of SAT. If the mind is an approximate X-solver, and X is complete for class C, that's important.

Improve this question
$\endgroup$
11
  • 19
    $\begingroup$ +1 for pointing out that surprisingly many real-life design challenges have some coNP flavour. It applies to engineering as well. If a machine breaks down or a bridge collapses, this is an easily verifiable proof that the design was bad, but how to prove that a design is good...? $\endgroup$
    – Jukka Suomela
    Commented Mar 9, 2011 at 17:30
  • 4
    $\begingroup$ Brains are physical devices, and therefore finite. The complexity class you're looking for is some proper subset of SPACE(O(1)) = TIME(O(1)). $\endgroup$
    – Jeffε
    Commented Mar 9, 2011 at 19:20
  • 15
    $\begingroup$ @JeffE: Computers are also physical devices, and therefore finite. Yet we still think that complexity classes help us understand computers (although not unequivocally, viz. the many discussions of "what if P=NP but the exponent or constants are huge"). On the other hand, the power of an individual computer increases on a much faster time scale than the power of an individual brain... $\endgroup$
    – Joshua Grochow
    Commented Mar 9, 2011 at 19:34
  • 4
    $\begingroup$ I think it was Punya Biswal who came up with this joke: the reason we have a difficult time coming up with explicit hard functions is that our brains are not powerful enough to imagine such functions :) $\endgroup$
    – arnab
    Commented Mar 9, 2011 at 21:13
  • 3
    $\begingroup$ Joshua: Theoretical computer scientists don't study computers; we study mathematical abstractions of computers. Give me a mathematical abstraction of a human brain, and you'll probably answer your own question. $\endgroup$
    – Jeffε
    Commented Mar 13, 2011 at 7:15

8 Answers 8

Reset to default
16
$\begingroup$

I don't claim this is a complete answer, but here are some thoughts that are hopefully along the lines of what you're looking for.

NP roughly corresponds to "puzzles" (viz. the NP-completeness of Sudoku, Minesweeper, Free Cell, etc., when these puzzles are suitably generalized to allow $n \to \infty$). PSPACE corresponds to "2-player games" (viz. the PSPACE-completeness of chess, go, etc.). This is not news.

People generally seem to do alright with finite instances of NP-complete puzzles, and yet find them non-trivial enough to be entertaining. The finite instances of PSPACE-complete games that we play are considered some of the more difficult intellectual tasks of this type. This at least suggests that PSPACE is "hitting the upper limits" of our abilities. (Yet our opponents in these PSPACE-complete games are generally other people. Even when the opponents are computers, the computers aren't perfect opponents. This heads towards the question of the power of interactive proofs when the players are computationally limited. There is also the technicality that some generalizations of these games are EXP-complete instead of PSPACE-complete.)

To an extent, the problem sizes that arise in actual puzzles/games have been calibrated to our abilities. 4x4 Sudoku would be too easy, hence boring. 16x16 Sudoku would take too much time (not more than the lifetime of the universe, but more than people are generally willing to sit to solve a Sudoku puzzle). 9x9 seems to be the "Goldilocks" size for people solving Sudoku. Similarly, playing Free Cell with a deck of 4 suits of 13 cards each and 4 free cells seems to be about the right difficulty to be solvable yet challenging for most people. (On the other hand, one of the smartest people I know is able to solve Free Cell games as though she were just counting natural numbers "1,2,3,4,...") Similarly for the size of Go and Chess boards.

Have you ever tried to compute a 6x6 permanent by hand?

I suppose the point is that if you take natural problems in classes significantly above PSPACE (or EXP), then the only finite instances that people are capable of solving seem to be so small as to be un-interesting. Part of the reason "natural" is necessary here is that one can take a natural problem, then "unnaturally" modify all instances of size $< 10^{10}$ so that for all instances a human would ever try the problem becomes totally intractible, regardless of its asymptotic complexity.

Conversely, for problems in EXP, any problem size below the "heel of the exponential" has a chance of being solvable by most people in reasonable amounts of time.

As to the rest of PH, there aren't many (any?) natural games people play with a fixed number of rounds. This is also somehow related to the fact that we don't know of many natural problems complete for levels of PH above the third.

As mentioned by Serge, FPT has a role to play here, but (I think) mostly in the fact that some problems naturally have more than one "input size" associated with them.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ chess and go are EXPTIME-complete rather than PSPACE-complete. This is the case typically for games whose duration can be exponential in the size of the board. $\endgroup$
    – Denis
    Commented Feb 5 at 12:40
  • 1
    $\begingroup$ @Denis: Thanks! I had thought there was some subtlety about the ko rule. Turns out there is, but the subtlety is not what I thought it was. It seems that with "full ko" rule (rather than the easier-to-check Japanese ko rule, where it is EXP-complete), Go is PSPACE-hard, but could be as hard as EXPSPACE-complete! $\endgroup$
    – Joshua Grochow
    Commented Feb 5 at 18:09
  • 1
    $\begingroup$ Indeed, this is a fun open problem :) $\endgroup$
    – Denis
    Commented Feb 5 at 20:49
  • $\begingroup$ I guess what I wrote holds for "worst-case" instances, which kind of makes sense for puzzles like Sudoku or games like chess. But for "real-world" instances sometimes we can go much farther. E.g. although computing Gröbner bases is EXPSPACE-complete, there are plenty of instances that arise "in practice" that can be solved by hand, and, despite being "small", are not so small as to be uninteresting. $\endgroup$
    – Joshua Grochow
    Commented Jun 26 at 20:44
13
$\begingroup$

The Tractable Cognition thesis postulates that human cognitive capacities are constrained by computational tractability. In this way, the P-Cognition thesis uses deterministic polynomial time as a model for computational tractability, while in the paper below, it is argued that the FPT-Cognition thesis is more appropriate. See Iris van Rooij's article in the June 2009 edition of the Parameterized Complexity Newsletter for a more detailed discussion and pointers to other papers.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Is there any evidence this is true? $\endgroup$
    – yters
    Commented Jul 7, 2018 at 18:11
13
$\begingroup$

I think one is led to the wrong model by trying to extrapolate from the kind of things the human brain appears to compute, and I think it would be better to take the opposite view and instead extrapolate from the computational model it is.

So, to me the complexity class that most reasonably captures the human mind is the nonuniform circuit class $TC^0$. This view is is supported by modeling the workings of the brain as a neural network performing computations in an instant.

Also, I do not agree with the statement in the question that the human mind can simulate a Turing machine. Rather, what it can do is to simulate the finite control of the Turing machine. To perform very complicated tasks, it seems necessary to be able to record information on a "tape".

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ With respect to the human simulation of a TM...I was assuming that humans are allowed reasonable resources, such as pencil and paper. Your point is fair though. $\endgroup$
    – user1338
    Commented Mar 10, 2011 at 0:42
  • 3
    $\begingroup$ Interesting viewpoint, but I don't think $TC^0$ quite gets at what the OP was asking. Integer division is complete for (a uniform version of) $TC^0$ under $AC^0$ reductions (according to the Zoo). Yet integer division has got to be close to one of the easiest tasks the human mind can perform. Maybe some more general version of neural networks would better fit here? $\endgroup$
    – Joshua Grochow
    Commented Mar 10, 2011 at 3:09
  • 4
    $\begingroup$ Writing down facts is without doubt one of the major reasons we progressed as humans and perhaps it also caused our brain to evolve. At the very least, it allow us to build a basis on which to build our ideas (e.g. imagine if TCS or any other field was based on speech only). On that ground, I believe that if you remove the "pencil and paper" human ability, you might as well remove the tape from the TM, and reduce it to a simple finite machine. $\endgroup$
    – chazisop
    Commented Mar 10, 2011 at 4:19
  • 2
    $\begingroup$ @Joshua: I agree, division (or multiplication, or just simple counting) is an easy task. But I think this argument is somewhat invalidated if you allow $AC^0$ reductions to division. Allow me to rephrase an old saying: For all we know, all of NEXP can be computed efficiently by depth 3 nonuniform circuits consisting of "division" gates. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Commented Mar 10, 2011 at 14:57
  • 2
    $\begingroup$ Fair point. I suppose if NEXP could be computed from such "simple" circuits, that would be pretty strong evidence that a brain made up of "just simple" neurons could really be quite powerful, which agrees with our experience. OTOH, I think the circuit of the brain has depth a lot higher than 3 :). $\endgroup$
    – Joshua Grochow
    Commented Mar 10, 2011 at 15:24
11
$\begingroup$

Complexity classes are defined in terms of asymptotic complexity, hence they don't map well to the cognitive abilities of humans, which are necessarily limited to bounded problem sizes.

The rule of the thumb is: if something is easy for a computer, then it may be hard for a human, vice versa, if it is hard for a computer it may be easy for a human.

Here "easy/hard for a computer" refers to practical tractability, not an abstract complexity class.

For instance, adding up a list of 1 billion integers is easy for a modern computer and difficult for a human, while producing a verbal description of a picture is easy for a human but difficult (currently impossible in the general case) for a computer.

Artificial Intelligence research showed that many cognitive tasks that humans and animals carry out easily, in some cases even subconsciously, can be modeled as NP-hard problems. Humans are not able to find optimal solutions to these problems for all sizes, but they are able to find heuristic solutions for practical sizes much better than the best known AI algorithms.

Also note that the left-brain vs right-brain distinction you mention is too simplistic and obsolete. Lateralization of brain functions is much more subtle, and may even vary from one individual to another.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ +1 for the first paragraph, -1 for everything else. MANY tasks are easy for both humans and computers, and MANY other tasks are hard for both. $\endgroup$
    – Jeffε
    Commented Mar 9, 2011 at 19:13
  • 2
    $\begingroup$ I thought it was obvious that there are trivial tasks which are easy for both humans and computers, anyway, I'm updating my answer to make it more explicit. $\endgroup$
    – Antonio Valerio Miceli-Barone
    Commented Mar 9, 2011 at 19:19
2
$\begingroup$

If we choose to study the human brain itself rather than how humans use their brain to solve problems,I don't believe this is an issue of complexity, but rather of computability. Since every TM needs a transition function, a human can imitate the TM's steps, therefore, the human brain is Turing-complete.

In the reverse direction, can TMs compute everything humans do? The short answer is we don't know. Assuming that the Church-Turing thesis is true, whether the answer will change or not depends on your view of the world (philosophical, spiritual , religious and other). In that case, we can safely say that the human brain itself as part of the material world, can be simulated by a Turing machine. The rest is up to debate and , at least in my opinion, not related to TCS.

One could argue that if $P \neq NP$ all problems in $NP-P$ would dwarf a lifetime. But we are talking about the power of the brain itself. The transition table and the work tape could be passed on from generation to generation until the answer is solved.Even if we require that problems solvable by humans do not exceed the lifetime of a single person, does $10^{10^{100}}n$ , which is just linear , seem like doable? I think not. One can argue that there is a TM that does the same in just $n$ using the speed-up theorem, but that would require storing $2 \log 10^{10^{100}}$ times more information in every step of the sped up algorithm. Of course, a specific lower bound would be needed to ensure a faster algorithm (constants included) does not exist.

So, if you would like to precisely calculate what problems the human brain, given the constraints of actual life, like distractions, attention span, etc. you should have an upper bound on the number of steps done in total, an upper bound on the number of steps done consecutively (even the most devoted researcher must sleep and eat), a limitation on the space (not just in the tape, but also in any "internal" registers), a simulation of how memory acts because unlike TMs , we can forget something we write in our "work tape" or the exact state, and of course, determine the relation between machine time steps and time in seconds or "human brain steps". Perhaps other issues would pop-up as you would go. In an ironic twist, perhaps one or more of this problem cannot be solved by the human brain, at least efficiently.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Assuming that a human has finite memory, it is not Turing complete. At most, it can simulate arbitrary finite state machines, up to some size. An immortal human with infinite paper, pencils, and patience would be Turing-complete. $\endgroup$
    – Antonio Valerio Miceli-Barone
    Commented Mar 9, 2011 at 19:11
  • $\begingroup$ @user1749, yeah, that's the idea actually. If you would like to view the human brain for what it is and not because it is linked to a human.Computers are turing complete but have a lifetime far smaller than any human's. I am sure a physical TM wouldn't last for millenia either. $\endgroup$
    – chazisop
    Commented Mar 9, 2011 at 19:26
2
$\begingroup$

Well, ${\bf ThC}_0$ is the class of functions a (polynomial size) neural net can solve in constant time. In polynomial time it could handle precisely $\bf{P}$, and in polylog time, $\bf NC$. But maybe we should allow exponentially many neurons and polynomial time? I believe this produces the counting hierarchy, built over $\bf \#P$. The number of levels of the hierarchy is, I believe, the number of times a neuron uses its ability to have exponential inflow.

Improve this answer
$\endgroup$
-1
$\begingroup$

If you give a human a pencil and paper she can solve nearly any problem, by acting like a machine. So I think this can't be the point.

Imho what makes human thinking is abstraction, i.e. humans don't run things (in the first place), they create views on stuff. Although, as I must admit, I cannot provide any nearly ready to use theory for abstraction.

|=

Improve this answer
$\endgroup$
-1
$\begingroup$

I have been thinking about this question for a long time. This is what I have come to :

We humans think usually in abstract mental objects and not in algorithms. The numbers we know, the language we speak, the thinking was once some abstract idea. These ideas were extended by philosophers, scientists and then put to use. What we have is different than how they originated.

Your question - "Which complexity class most precisely captures the totality of what human beings can accomplish with their minds?" can be answered only if there is enough proof that humans follow mathematical/algorithmic/probabilistic models. Well, they might follow each ones of the above or combination of them. But they are actually something different. This is just normal human thinking. Breaking down the creative thoughts like Mozart's composition, a poem or the thinking of a sportsman in respective formal ways(mathematical/logical methods of their thinking) and trying to generalize would be quite a feat, not sure if that will be possible though.

I also think we might approximate the complexity class, but we can never be sure.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.