On Nontrivial Separators for kPage Graphs and Simulations by Nondeterministic OneTape Turing Machines
 Title:

On Nontrivial Separators for kPage Graphs and Simulations by Nondeterministic OneTape Turing Machines
 Author(s):

Galil, Zvi
Kannan, Ravi
Szemeredi, Endre
 Date:

1987
 Type:

Technical reports
 Department(s):

Computer Science
 Persistent URL:

http://hdl.handle.net/10022/AC:P:11871
 Series:

Columbia University Computer Science Technical Reports
 Part Number:

CUCS30187
 Publisher:

Department of Computer Science, Columbia University
 Publisher Location:

New York
 Abstract:

We show that the following statements are equivalent: 1. Statement 1. 3pushdown graphs have sublinear separators. 2. Statement 1∗. kpage graphs have sublinear separators. 3. Statement 2. A onetape nondeterministic Turing machine can simulate a twotape machine in subquadratic time. None of the statements is known to be true or false at present. However, our proof of equivalence is quantitativeit relates exactly the separator size of the two kinds of graphs to the running time of the simulation in Statement 2. Using this equivalence we derive several graphtheoretic corollaries. There are known examples where upper bounds on graph properties imply upper bounds on computation time or space. There are other examples where lower bounds on graph properties are used to derive lower bounds on computation time in restricted settings. However, our results may constitute the first example where a graph problem is shown to be equivalent to a problem in computational complexity. In a companion paper we construct graphs and prove a lower bound or their separators. Using the equivalence we prove an almost linear lower bound for the size of separators for 3pushdown graphs and an almost quadratic lower bound for simulating twotape nondeterministic Turing machines by onetape machines. Specifically, for an integers s let ls(n), the siterated logarithm function, be defined inductively: l°(n)=n, ls+1(n)=log2(ls(n)) for s⩾0. Then: 1. For every fixed s and all n, there is an nvertex 3pushdown graph whose smallest separator contains at least ω(n/ls(n)) vertices.2. There is a language L recognizable in real time by a twotape nondeterministic Turing machine, but every online onetape nondeterministic Turing machine that recognizes L requires ω(n2/ls(n)) time for any positive integer.
 Subject(s):

Computer science
 Item views
 170
 Metadata:

text  xml
 Suggested Citation:
 Zvi Galil, Ravi Kannan, Endre Szemeredi, 1987, On Nontrivial Separators for kPage Graphs and Simulations by Nondeterministic OneTape Turing Machines, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:11871.