Cons-free Programs and Complexity Classes between logspace and ptime

Let $X\subseteq\{0,1\}^{*}$ be a set of bit strings. The decision problem for $X$: given $x\in\{0,1\}^{*}$, to decide whether or not $x\in X$. We say that $X$ is in ptime iff it is decidable by a 1-tape deterministic Turing machine that runs within polynomial time $O(n^{k})$ [here $n=|x|$ is the length of its input $x$, and $k$ is a constant independent of $x$]. Further, $X$ is in logspace iff it is decidable by a 2-tape Turing machine that uses at most $O(\log n)$ bits of storage space on tape 2, assuming its $n$-bit input is given on read-only tape 1. Both problem classes are of practical interest as they are decidable by programs with running times bounded by polynomial functions of their input lengths. The essential difference is the amount of allowed storage space. These classes are invariant across a wide range of variations among computation models, and it is easy to see that $\mbox{\sc logspace}\subseteq\mbox{\sc ptime}$.

However, the question: is $\mbox{\sc logspace}\subsetneq\mbox{\sc ptime}?$ has stood open for many years.

All programs are first-order in this paper,⁵⁵5The larger language described in [9] encompasses both first and higher-order programs. and deterministic to begin with (until nondeterminism is expressly added in Section 5). First, a brief overview (details in [7, 8, 9]):

The full inference rule set is given in Figure 1. It is essentially the first-order part of Fig. 1 in [9].

Axioms have no premises at all, and base function calls have exactly one premise, making their tree construction straightforward. The inference rules for conditional expressions have two premises, and a call to an $m$-ary function has $m+1$ premises. We choose to evaluate the premises left-to-right. For the case if e₀ then e₁ else e₂ $\to?$, there are two possibly applicable inference rules. However both possibilities begin by evaluating e₀: finding $v$ such that e₀ $\to v$. Once $v$ is known, only one of the two if rules can be applied.

Claim. the evaluation order above for given p and $\mathit{input}$ is general: if $\mbox{$[[$}{\tt p}\mbox{$]]$}(input)=v$ is deducible by any finite proof at all, then the evaluation order will terminate with result $\mbox{$[[$}{\tt p}\mbox{$]]$}(input)=v$ at the root.

A consequence: tree ${\cal T}^{{\tt p},x}$ is unique if it exists, so CF is a deterministic language. (Nondeterministic variants of CF will considered later.)

Proof: a straightforward induction on the depth of computation trees. If the entry function definition is f x = e^f, then the root $\mbox{$[[$}{\tt p}\mbox{$]]$}(x)=v$ has a parent of the form ${\tt p},\rho_{0}\vdash{\tt e}^{\tt f}\to v$ where the initial environment is $\rho_{0}=[{\tt x}\mapsto x]$. Of course $x$ is a suffix of $x$. At any non-root node in the computation tree, any new value must either be a Boolean constant or [], or constructed by a base function not, head, tail, or null from a value already proven to be in $V_{x}$.

Proof: By Lemma 2, any argument of any $m$-ary p function f has at most $\#V_{x}=3+|x|$ possible values, so the number of reachable argument tuples for f can at most be $(3+|x|)^{m}$.

Remark: this does not necessarily imply that p’s running time is polynomial in $|x|$. We say more on this in Section 2.

To more clearly define space usage and present the tail call optimisation, we use a finer, more operational level of detail based on traditional implementations⁶⁶6Readers may think of machine-code run-time states, e.g., value stacks, stack frames,…; or of tapes and state transition relations. Such implementation paraphernalia are well-known both to compiler writers and programming language theorists.. Programs are executed sequentially as in the proof-tree-building algorithm seen earlier. The expression on the right side of a function definition is evaluated one step at a time as in Section 1.3; but with an extra data structure, a stack $\sigma$ used to record some of the environments seen before. The stack’s topmost activation record corresponds closely to the current environment $\rho$.

Each defined function f x1...xm = e has an activation record format that contains the values $v_{1},\ldots,v_{m}$ of the arguments with which f has been called (plus shorter-lived “temporary results,” i.e., as-yet-unused subexpression values). On any call to f, a new activation record is pushed onto the stack $\sigma$. This activation record will be popped when control returns from the call.

Proof: in the call history of p on input $x$, all runtime configurations must be distinct (else the program is in an infinite loop). There is a constant bound on the number of stack frames. Thus, by Lemma 3 there are only polynomially many distinct runtime configurations.

First, a trivial example with non-polynomial running time (from [9]):

It is easy to see that $\mathit{time}_{\tt q}(x)=2^{O(|x|)}$ due to the repeated calls to tail x. Exponential time is not necessary, though, since the computed function satisfies f(x) = True.

$MCV$ is the Monotone Circuit Value Problem. Technically it is the set of all straight-line Boolean programs whose last computed value is True, e.g.,

$x_{0}:={\tt False};\ x_{1}:={\tt True};\ x_{2}:=x_{1}\lor x_{0};\ x_{3}:=x_{2}\land x_{0};\ x_{4}:=x_{3}\lor x_{2};\ x_{5}:=x_{4}\lor x_{3}$

Following is the core of a Haskell program to decide membership in $MCV$, together with a sample run. We chose a compact Boolean program representation, so the program above becomes a list:

• 
  

  program = [ OR 5 4 3, OR 4 3 2, AND 3 2 0, OR 2 1 0 ]
  

• 
  

  type Program = [Instruction]
  data Instruction = AND Int Int Int | OR Int Int Int
  
  mcv :: Program -> Bool
  vv :: (Int,Program) -> Bool
  
  mcv ((OR lhs x y):s) = if vv(x,s) then True else vv(y,s)
  mcv ((AND lhs x y):s) = if vv(x,s) then vv(y,s) else False
  
  vv(0,s) = False -- vv(v,s) = value of variable v at program suffix s
  vv(1,s) = True --
  vv(v,s) = case s of
  ((AND lhs x y):s’) -> if v==lhs then mcv(s) else vv(v,s’)
  ((OR lhs x y):s’) -> if v==lhs then mcv(s) else vv(v,s’)
  
  

The beginning 1,1,1,0 of the program code gives (in unary) the code block length, $3$ for this program. A Boolean assignment xi := xj op xk is coded as $\hat{\tt i}\ \hat{\tt op}\ \hat{\tt j}\ \hat{\tt k}$, where the Boolean operators $\lor,\land$ are coded as 0, 1 respectively.

Using this encoding, it is not hard to transform the Haskell-like program to use if-then-else statements rather than case; and then implement it in the true CF language.

• •

  For $\supseteq$, we simulate a CFTR program p by a logspace Turing machine (informal). Given an input $x=a_{1}\ldots a_{n}\in\{0,1\}^{*}$, by Lemma 2 any reachable configuration $({\tt f},\rho)$ satisfies $0\leq|\rho({\tt xi})|\leq\max(n,1)$ for $i=1,\ldots,m$. Each $v_{i}$ can be coded in $O(\log n)$ bits. Now f and the number of f’s arguments are independent of $x$, so an entire configuration $({\tt f},\rho)$ can be coded into $O(\log n)$ bits.

  The remaining task is to show that the operational semantics of running p on $x$ can be simulated by a logspace Turing machine. The key: because p is tail recursive, there is no nesting of calls to program-defined functions. The construction can be described by cases:

  1. 1.

     Expressions without calls to any defined function: Suppose p’s current environment $\rho$ is represented on the Turing machine work tape. Simulating this evaluation is straighforward.

  2. 2.

     Evaluation of an expression f e1…em: Since p is tail recursive, none of e1,...,em contains a call, and there is “nothing more to do” after the call f e1…em has been simulated. Assume inductively that e1…em have all been evaluated. Given the definition f x1…xm = e of f, the remaining steps¹⁰¹⁰10These steps are done using Turing machine representations of the environments as coded on Tape 2. are to collect the values $v_{1},\ldots,v_{m}$ construct a new environment $\rho^{\prime}=[{\tt x1}\mapsto v_{1},\ldots,{\tt xm}\mapsto v_{m}]$, and replace the current $\rho$ by $\rho^{\prime}$.

• •

  For $\subseteq$, we simulate a logspace Turing machine by a CFTR program. This can be done using Lemma 2: represent a Tape 2 value by one or more suffixes of $x$. (A more general result is shown in [9] by “counting modules”.)

• •

  For $\subseteq$, we simulate a ptime Turing machine $Z$ by a CF program. (this is the core of Proposition 6.5 from [9]). Assume Turing machine $Z=(Q,\{0,1\},\delta,q_{0})$ is given¹¹¹¹11As usual $Q$ is a finite set with initial state $q_{0}$, and transition function of type $\delta:Q\times\{0,1,B\}\to Q\times\{0,1,B\}\times\{0,1,-1\}$. A total state is a triple $(q,i,\tau)$ where $q\in Q,i\geq 0$ and the tape is $\tau:{\mathbb{N}}\to\{0,1,B\}$. Scan positions are counted $i=0,1,\ldots$ from the tape left end. Transition $\delta(q,a)=(q^{\prime},a^{\prime},d)$ means: if $Z$ is in state $q$ and $a=\tau(i)$ is the scanned tape symbol, then change the state to $q^{\prime}$, write $a^{\prime}$ in place of the scanned symbol, and move the read head from its current position $i$ to position $i+d$. and that it runs in time at most $n^{k}$ for inputs $x$ of length $n$. Consider an input $x={\tt a}_{1}{\tt a}_{2}\ldots{\tt a}_{n}\in\{{\tt 0},{\tt 1}\}^{*}$.

  Idea: in the space-time diagram of $Z$’s computation on $x$ (e.g., Fig. 3 in [9]), data propagation is local; the information (control state $q$, symbol $a$, whether or not it is scanned) at time $t$ and tape position $i$ is a mathematical function of the same information at time $t-1$ and tape positions $i-1,i,i+1$. This connection can be used to compute the contents of any tape cell at any time. Repeating for $t=0,1,\ldots,n^{k}$ steps gives the final result of the computation ($x$ is accepted or not accepted).

  The simulating CF program computes functions

  ${\tt state}(t)$	=	the state $q$ that $Z$ is in at time $t$
  ${\tt position}(t)$	=	the scanning position $i\in\{0,1,2,\ldots,n^{k}\}$ at time $t$
  ${\tt symbol}(t,i)$	=	the tape symbol $a$ found at time $t$ and scanning position $i$

  Initially, at time $t=0$ we have total state $(q_{0},0,\tau_{0})$ where $\tau_{0}(i)={\tt a}_{i}$ for $1\leq i\leq n$, else $\tau_{0}(i)=B$. Now suppose $t>0$ and the total state at time $t-1$ is $(q,i,\tau)$, and that $\delta(q,a)=(q^{\prime},a^{\prime},d)$. Then the total state at time $t$ will be $(q^{\prime},i+d,\tau^{\prime})$ where $\tau^{\prime}(i)=a^{\prime}$ and $\tau^{\prime}(j)=\tau(j)$ if $j\neq i$.

  Construction of a CF program z with definitions of state, position and symbol is straightforward. Arguments $t,i\in\{0,1,2,\ldots,n^{k}\}$ can be uniquely encoded as tuples of suffixes of $x={\tt a}_{1}{\tt a}_{2}\ldots{\tt a}_{n}\in\{{\tt 0},{\tt 1}\}^{*}$. It is not hard to see that such an encoding is possible; [9] works out details for an imperative version of the Turing machine (cf. Fig. 5).

• •

  For $\supseteq$, we simulate an arbitrary CF program p by a ptime Turing machine (call it $Z_{\tt p}$). We describe the $Z_{\tt p}$ computation informally. Given an input $x\in\{0,1\}^{*}$, $Z_{\tt p}$ will systematically build a cache containing $\mathit{Reach}_{\tt p}(x)$. By Lemma 3 its size is polynomially bounded.

  The cache (call it $c$) at any time contains a set of triples $({\tt f},\rho,v^{\prime})$ where the simulator has completed evaluation of function f on argument values in environment $\rho$, and this f call has returned value $v$.

  Concretely, $c$ is built “breadth-first”: when a p call f e1…em is encountered (initially $c$ is empty):

  • –

    First, arguments e1,…,em are evaluated to values $v_{1},\ldots,v_{m}$; and these are collected into an environment $\rho$.

  • –

    Second, cache $c$ is searched. If it contains $({\tt f},\rho,v)$, then simulation continues using the value $v$ as the value of f e1…em.

  • –

    If $c$ contains no such triple, then p must contain a function definition f x1...xm = e^f. Then expression e^f is evaluated in environment $\rho$ to yield some value $v$. After finishing, add the triple $({\tt f},\rho,v)$ to $c$, and return the value $v$.

This can be seen in the proof that $\mbox{\sc ptime}\supseteq\mbox{\mbox{$\mathbf{\{\{}$}\rm{CF}\mbox{$\mathbf{\}\}}$}}$: the value of ${\tt symbol}(t+1,i)$ may depend on the values of ${\tt symbol}(t,i-1)$, and ${\tt symbol}(t,i)$, and ${\tt symbol}(t,i+1)$. In turn, the value of ${\tt symbol}(t,i)$ may depend on the values of ${\tt symbol}(t-1,i-1)$, and ${\tt symbol}(t-1,i)$, and ${\tt symbol}(t-1,i+1)$.

Net effect: a symbol a_i on the final tape (with $t=n^{k}$) may depend many distinct function call sequences that “bottom out” at $t=0$. The number of call sequences may be exponential in $n$.

Unfortunately, it is is hard to see which calls will overlap (it seems impossible without storage). Furthermore, the “caching” technique used to prove Theorem 2 cannot be used because, in contrast with Turing machines, CF programs do not have a memory that can accumulate previously computed values.

However it is not known whether $\mathbf{\{\{}$CFpoly$\mathbf{\}\}}$ is closed under nondeterminism, since Bonfante and Cook’s reasoning does not seem to apply. Why? The memoisation used in [3] yields a Turing machine polynomial time algorithm. Consequently, the problem is decidable by some CF program; but we know no way to reduce its time usage from exponential to polynomial.

The idea of applying tail-recursion to the largest subtree to save space was also used to implement Quicksort [10]. However our problem is much more general; and we must use nondeterminism because it cannot be known in advance which subtree will be the largest.