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:

Computer Science

Permanent URL:

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

Series:

Columbia University Computer Science Technical Reports

Part Number:

CUCS30187

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:

150
 Metadata:

text  xml