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 Neciporuk 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 (is contained in) D}. This is interpreted as allowing to pick, as the D-value of a node labelled f with left child l and right child r, any value from f(D-value of l, 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].
展开▼
