Can Chimps Go It Alone?

Consider a smart chimpanzee named M from a tribe afflicted with a form of Alzheimer’s disease. Think of M as a logspace-bounded Turing machine. M can do simple things like integer arithmetic and matrix multiplication, but M turns sullen and calls for help when asked to perform seemingly equally simple tasks, such as simulating deterministic tree and dag automata.

Is M acting difficult or is she just not smart enough?

Even before the P versus NP question, Cook [3] conjectured that no amount of smarts can compensate for Alzheimer’s disease.

We will review some of the attempts at separating L from P inspired by pebbling arguments. Emphasis will be placed on branching programs for the tree evaluation problem, recently studied anew [2]. The problem consists of determining the value that percolates to the root of a (binary) tree when a value from a domain D is prescribed at each tree leaf and an explicit function f:D×D → D is prescribed at each internal node. In a nutshell, lower bounds for restricted branching programs can be proved, but approaches to attack the general model strangely come up against the same barrier that Nec̆iporuk encountered in a two-page note 50 years ago and that still stands today.

Tree evaluation naturally extends to tree generation [1], where the functions f:D×D → D at internal tree nodes are replaced with functions f:D×D → {S : S ⊆ D}. This is interpreted as allowing to pick, as the D-value of a node labelled f with left child ℓ and right child r, any value from f(D-value of ℓ, D-value of r). Tree generation can then be turned into a monotone boolean function. Strong lower bounds for this function have been derived from pebbling intuition [4,1] and we will further discuss some of these.

For a suitable bibliography please consult [2,4,1].

Authors and Affiliations

1. Université de Montréal and Chaire Digiteo ENS Cachan-École Polytechnique, Canada

   Pierre McKenzie

Editors and Affiliations

1. Department of Computer Science, Middlesex College, Western University, N6A 5B7, London, ON, Canada

   Helmut Jurgensen

2. Departamento de Ciência de Computadores, Universidade do Porto, Faculdade de Ciências, Rua do Campo Alegre 1021-1055,, 4169-007, Porto, Portugal

   Rogério Reis

Reprints and permissions

© 2013 Springer-Verlag Berlin Heidelberg

Policies and ethics