5

Suppose that instead of the usual linear work tape the input is given in a binary tree structure with n leaves and log n depth, the initial position being the root. At every node, we can step to its parent, left child or right child.

I am interested in what "tree-languages" can be accepted by what machines. More specifically, take the language where in every non-leaf we have the gate of a boolean circuit (ie. and or not), in the leaves either a constant or a variable (different for each leaf) and such a "tree-word" is in the language if and only if it has a satisfying assignment. Can this language be decided by a turing machine that has an o(log n) space worktape?

Note that it is accepted by a non-deterministic finite state machine and also by a deterministic turing machine with O(log n) space. Similarly, if all the variables are constant, then it can be decided by a deterministic finite state machine. (If there are no constants, then every formula is satisfiable.)

domotorp
  • 13,931
  • 37
  • 93
  • 1
    Could you please elaborate a bit more why the language accepted by a non-deterministic finite state machine and by a deterministic turing machine with O(log n) space? Even when formulas are balanced, I believe the satisfiability problem for them is still complete for $\mathsf{NP}$. – Dai Le Dec 27 '10 at 14:16
  • 1
    Because we can use that the input is not given on a linear tape, but rather on a tree-structure. Eg. if all the variables are constant, then the following deterministic approach works: Start from the leftmost leaf. Its output is 0 or 1. Suppose it is a 1. Go to the gate above it. If it is an OR gate, we already know it is true, we can go to the gate above. If it is an AND gate, then we have to go down to check the right child of the gate. In general, we only check the right child of the gate, if it is undecided by the left one. This way we never have to store any information. – domotorp Dec 27 '10 at 19:34
  • 1
    @domotorp: Of course, the case of constant inputs is trivial. But you seem to claim that for the not all constant input case that you can still "accept" in deterministic $O(\log n)$. Maybe you meant verifying if a truth assignment is a satisfying one? The word "accept" is misleading to me. In any case, the problem of evaluating a balanced boolean formula on a given truth assignment is complete for $\mathsf{NC}^1$. – Dai Le Dec 27 '10 at 21:38
  • 1
    I think Dai is right, and moreover evaluating a given balanced Boolean formula without variables (i.e. only using $\land, \lor, \lnot, \top, \bot$) is still $NC^1$-complete. This is true even for monotone case (i.e. without $\lnot$). – Kaveh Dec 28 '10 at 03:21
  • 1
    @Dai Le and Kaveh: It seems we misunderstand each other. I only wrote down this case as the others are similar. If you want to accept in non-det constant space, you simply guess a satisfying evaluation and do as before. If you have a logspace turing machine, then you have to remember the possible left inputs (0, 1, or both) of each gate along the path that you walked down, this takes log n space (you could even use a stack machine). My evaluation problem is not NC^1-complete because the reading head can move on the given tree-structure of the input. – domotorp Dec 28 '10 at 07:49
  • 1
    @Dai: Note that no variables are repeated. – Kristoffer Arnsfelt Hansen Dec 28 '10 at 10:34

2 Answers2

7

It seems to me that the problem can be solved in constant space.

We perform a recursive procedure, and store only the parity of the number of negation gates seen on the path from the root to the current node.

At a leaf, if we have a variable and have seen an even number of negation gates, we set the variable to be true. Otherwise, if we have seen an odd number of negation gates, we set the variable to be false.

As before, at an AND or OR gate we first call recusively to the left, and then to the right if the value has not been determined.

Now if there exists a satisfying assignment, then the assignment defined above will satisfy the formula.

Kristoffer Arnsfelt Hansen
  • 4,159
  • 2
  • 26
  • 36
  • 1
    Brilliant! My next question would be to find a language that separates deterministic and non-deterministic machines, my ultimate amibtious goal would be the following separation: http://cstheory.stackexchange.com/questions/3963/does-loglog-nloglog – domotorp Dec 28 '10 at 14:53
  • 2
    What a nice solution! I wish that domotorp had explained his question better though. – Dai Le Dec 28 '10 at 17:35
-1

From the question I assume you are talking about exact algorithms and not approximate ones. Since this is the case, you will have to "write" the entire input, using the same space as before, just using a different structure. Although this might provide a speedup in time, the space used will be at least the same, assuming that you use a reasonably efficient representation (e.g. not a unary one).

Using less tape is usually achieved by space re-use or by carefully selecting which cells to overwrite, so that you can use some information later on the computation. However usually you cannot re-use or overwrite the input, since you need it throughout the process of solving the problem.

Even if the above problems were dealt with, the usual model for space complexity has a separate input tape, which is read only and is not measured as used space , so we can have sublinear space complexities and avoid the problems above. Perhaps you are referring to a different model?

chazisop
  • 3,796
  • 2
  • 29
  • 37
  • 2
    The input is read only, we don't have to "write" it, just read it, as is the usual case with sublinear space complexity classes. So this is the model I consider. Approximation does not make any sense, as this is a decision problem and not a parameter that we want to compute. – domotorp Dec 27 '10 at 08:01
  • Since this problem is in NP, the search problem introduces at most a polynomial ( I think it is $O(n^{2})$ ) overhead. I was considering the search problem when talking about approx. Anyway, I still don't understand why we count the input as part of the space used. – chazisop Dec 28 '10 at 12:39