A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes

Till Tantau

Facets of Complexity, September 2016

Outline

Algorithmic Metatheorems Classic Variants … … and New Variants

New Variants 1: Space Complexity New Theorems Applications: Cycle Lengths in Graphs

Applications: Quantifier Prefix Classes Applications: Integer Optimization

New Variants 2: Circuit Complexity New Theorems Applications: Visible Pushdown Languages

A Well-Known Problem

Public Domain

We install WLAN routers in a home. Adjacent routers interfere. The abstract problem is of course 3-colorability.

Public Domain

We install WLAN routers in a home. Adjacent routers interfere. The abstract problem is of course 3-colorability.

Public Domain

We install WLAN routers in a home. Adjacent routers interfere. The abstract problem is of course 3-colorability.

We install WLAN routers in a home. Adjacent routers interfere. The abstract problem is of course 3-colorability.

Hi! Is this the ‘‘facets of complexity’’ chat?

Bingo!

Ok, I’m a bit of newbie to this theory stuff.

Welcome anyway.

Ok, guys, here is my question: I know 3-colorability is NP-complete. But can I still solve it using divide and conquer?

No.

That’s it? Just ‘‘No’’?

Yes.

Well, if your input happens to allow a tree-like decomposition, things might be different.

A what?

I can explain that to you, but I will need some time.

Oh, I have about 50 minutes left…

Till Tantau Facets of Complexity, September 2016 4/ 48

Divide and Conquer, First Attempt

Entzwei und gebiete!

Tüchtig Wort. – Verein und leite!

Besserer Hort.

Divide and Conquer, First Attempt

Johann Wolfgang Goethe Sometimes divide and conquer can be applied to 3-colorability.

Pick two appropriate vertices and consider the 6 possible colorings. A vertex screens part of the graph and we can solve the problem recursively on the independent parts. It can happen that we have to remember several vertices during the recursion.

Sometimes divide and conquer can be applied to 3-colorability.

Pick two appropriate vertices and consider the 6 possible colorings. A vertex screens part of the graph and we can solve the problem recursively on the independent parts. It can happen that we have to remember several vertices during the recursion.

Sometimes divide and conquer can be applied to 3-colorability.

Pick two appropriate vertices and consider the 6 possible colorings. A vertex screens part of the graph and we can solve the problem recursively on the independent parts. It can happen that we have to remember several vertices during the recursion.

Sometimes divide and conquer can be applied to 3-colorability.

Pick two appropriate vertices and consider the 6 possible colorings. A vertex screens part of the graph and we can solve the problem recursively on the independent parts. It can happen that we have to remember several vertices during the recursion.

Sometimes divide and conquer can be applied to 3-colorability.

Pick two appropriate vertices and consider the 6 possible colorings. A vertex screens part of the graph and we can solve the problem recursively on the independent parts. It can happen that we have to remember several vertices during the recursion.

Sometimes divide and conquer can be applied to 3-colorability.

Pick two appropriate vertices and consider the 6 possible colorings. A vertex screens part of the graph and we can solve the problem recursively on the independent parts. It can happen that we have to remember several vertices during the recursion.

Sometimes divide and conquer can be applied to 3-colorability.

Pick two appropriate vertices and consider the 6 possible colorings. A vertex screens part of the graph and we can solve the problem recursively on the independent parts. It can happen that we have to remember several vertices during the recursion.

Sometimes divide and conquer can be applied to 3-colorability.

Pick two appropriate vertices and consider the 6 possible colorings. A vertex screens part of the graph and we can solve the problem recursively on the independent parts. It can happen that we have to remember several vertices during the recursion.

Divide and Conquer, First Attempt

A game describes how we can proceed.

Till Tantau Facets of Complexity, September 2016 5/ 48

Robbers and Coppers

Game Objective The k cops try to catch a robber by being on the same vertex as her.

Game Rules

1. First the cops, then the robber pick a start vertex.

2. A cop gets on a helicopter and heads towards some vertex.

3. Meanwhile the robber moves along unoccupied vertices.

Robbers and Coppers:

Two Cops Do Not Catch the Robber.

a b c d e f g h i j k l

Go

Till Tantau Facets of Complexity, September 2016 7/ 48

Robbers and Coppers:

Three Cops Always Catch the Robber.

a b c d e f g h i j k l

Go

Till Tantau Facets of Complexity, September 2016 8/ 48

The Cops’s Strategy = Tree Decomposition

The winning strategy of the cops forms a tree: The nodes are positions of the cops. The root is their initial position. The children of a tree node are the graph components that could contain the robber.

Example of a Tree Decomposition of Width 2.

Till Tantau Facets of Complexity, September 2016 10/ 48

Divide and Conquer, Second Attempt

Theorem

For a graph G let a tree decomposition of width k with n nodes be given. Then we can decide in time O(3^{k+1}n) whether G is 3-colorable.

Theorem

For a graph G let a tree decomposition of width k with n nodes be given. Then we can compute in timeO(2^{k+1}n) the largest independent set of G.

Divide and Conquer, Second Attempt

Theorem

For a graph G let a tree decomposition of width k with n nodes be given. Then we can decide in time O(3^{k+1}n) whether G is 3-colorable.

Theorem

For a graph G let a tree decomposition of width k with n nodes be given. Then we can compute in timeO(2^{k+1}n) the largest independent set of G.

Why We Need Meta theorems.

Till Tantau Facets of Complexity, September 2016 12/ 48

Algorithmic Metatheorems Classic Variants … … and New Variants

New Variants 1: Space Complexity New Theorems Applications: Cycle Lengths in Graphs

Applications: Quantifier Prefix Classes Applications: Integer Optimization

New Variants 2: Circuit Complexity New Theorems Applications: Visible Pushdown Languages

All Problems Share one Property.

In 1990, Courcelle noted that all of the problems can be described in monadic second order logic (MSO logic).

Till Tantau Facets of Complexity, September 2016 14/ 48

A Logical Formula Specifying 3-Colorability.

⊧^{?} \underbrace{∃R∃G∃B∀x∀y}_{PatternE_{1}E_{1}E_{1}aa}(E(x y) →

((R(x) ∧ ¬G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ ¬G(x) ∧ B(x))) ∧ ¬(R(x) ∧ R(y)) ∧ ¬(G(x) ∧ G(y)) ∧ ¬(B(x) ∧ B(y)))

((R(x) ∧ ¬G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ ¬G(x) ∧ B(x))) ∧ ¬(R(x) ∧ R(y)) ∧ ¬(G(x) ∧ G(y)) ∧ ¬(B(x) ∧ B(y)))

((R(x) ∧ ¬G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ ¬G(x) ∧ B(x))) ∧ ¬(R(x) ∧ R(y)) ∧ ¬(G(x) ∧ G(y)) ∧ ¬(B(x) ∧ B(y)))

((R(x) ∧ ¬G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ ¬G(x) ∧ B(x))) ∧ ¬(R(x) ∧ R(y)) ∧ ¬(G(x) ∧ G(y)) ∧ ¬(B(x) ∧ B(y)))

A Logical Formula Specifying 3-Colorability.

\begin{matrix}x \\ y \end{matrix} ⊧ \underbrace{∃R∃G∃B∀x∀y}_{PatternE_{1}E_{1}E_{1}aa} (E(x y) →

((R(x) ∧ ¬G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ ¬G(x) ∧ B(x))) ∧ ¬(R(x) ∧ R(y)) ∧ ¬(G(x) ∧ G(y)) ∧ ¬(B(x) ∧ B(y)))

A Logical Formula Specifying 3-Colorability.

\begin{matrix}x \\ y \end{matrix} ⊧ \underbrace{∃R∃G∃B∀x∀y}_{PatternE_{1}E_{1}E_{1}aa} (E(x y) →

((R(x) ∧ ¬G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ ¬G(x) ∧ B(x))) ∧ ¬(R(x) ∧ R(y)) ∧ ¬(G(x) ∧ G(y)) ∧ ¬(B(x) ∧ B(y)))

Classical Algorithmic Metatheorems.

Theorem (Courcelle) Let be an MSO formula and k a number. Then

{G | G ⊧ and G has tree width at most k } can be decided in linear time.

Proof Sketch

Step 1: The original question.

⊧ _{3-colorable} ?

Till Tantau Facets of Complexity, September 2016 17/ 48

Proof Sketch

Step 2: Compute a tree decomposition in linear time.

Proof Sketch

Step 3: Adjust the formula so that it applies to the tree. ⊧ ′_{3-colorable} ?

Proof Sketch

Step 4: Transform the formula into a tree automaton. ∈ L(M_{3-colorable})?

Proof Sketch

Step 5: Evaluate that automaton in linear time. q_{0} q_{0} q_{0} q_{0} q_{0}

Proof Sketch

Step 5: Evaluate that automaton in linear time. q_{3} q_{0} q_{2} q_{0} q_{0} q_{0} q_{5} q_{0}

Proof Sketch

Classical Algorithmic Metatheorems.

Step 5: Evaluate that automaton in linear time. q_{5} ∈ Q_{accepting}? q_{3} q_{0} q_{2} q_{0} q_{0} q_{8} q_{0} q_{5} q_{0} Theorem (The General Pattern) If

the problem can be described in a certain logic and the input can be decomposed in a certain way,

then there is a certain kind of algorithm for it.

Theorem (Courcelle) If

the problem can be described in MSO logic and the input has tree width at most k,

then there is a linear time of algorithm for it.

Theorem (Bodlaender, Courcelle) If

the problem can be described in MSO logic and the input has tree width at most k,

then there is a parallel algorithm running in time O(log n).

Theorem (Courcelle, Makowsky, Rotics) If

the problem can be described in MSO logic and the input has clique width at most k,

then there is a polynomial time algorithm for it.

Theorem (Frick, Grohe) If

the problem can be described in FO logic and the input is planar,

then there is a linear time algorithm for it.

Theorem (Flum, Grohe) If

the problem can be described in FO logic and the input has a forbidden minor,

then there is a polynomial time algorithm for it.

Algorithmic Metatheorems Classic Variants … … and New Variants

New Variants 1: Space Complexity New Theorems Applications: Cycle Lengths in Graphs

Applications: Quantifier Prefix Classes Applications: Integer Optimization

New Variants 2: Circuit Complexity New Theorems Applications: Visible Pushdown Languages

Beyond Time

While the classical theorems yield tight upper time bounds… … they yield no completeness results. The new metatheorems concern

space complexity and circuit complexity

and yield completeness results.

Algorithmic Metatheorems Classic Variants … … and New Variants

New Variants 1: Space Complexity New Theorems Applications: Cycle Lengths in Graphs

Applications: Quantifier Prefix Classes Applications: Integer Optimization

New Variants 2: Circuit Complexity New Theorems Applications: Visible Pushdown Languages

A Logspace Turing Machine

Input tape (read only), n symbols 3401234*3143223 Work tape, O(log n) symbols 42

M

Till Tantau Facets of Complexity, September 2016 23/ 48

The Logspace Version of Courcelle’s Theorem.

Theorem (Elberfeld, T, Jakoby, 2010) Let be an MSO formula and k a number. Then

{G | G ⊧ and G has tree width at most k } can be decided in logspace.

The Low-Hanging Fruits.

Corollary For all k, we can solve in logspace:

{G | G is 3-colorable and G has tree width at most k}.

{G | G has a perfect matching and G has tree width at most k}.

{(G s t) | t is reachable from s and G has tree width at most k}.

…

(Each result used to be a paper.)

Till Tantau Facets of Complexity, September 2016 25/ 48

Algorithmic Metatheorems Classic Variants … … and New Variants

New Variants 1: Space Complexity New Theorems Applications: Cycle Lengths in Graphs

Applications: Quantifier Prefix Classes Applications: Integer Optimization

New Variants 2: Circuit Complexity New Theorems Applications: Visible Pushdown Languages

The High-Hanging Fruits.

Metatheorems make statements about decomposable graphs.

For arbitrary graph, this may work:

If the graph is decomposable, apply the metatheorem.

If the graph is not decomposable, it must have many edges, which we may use algorithmically.

Till Tantau Facets of Complexity, September 2016 27/ 48

The Formula _{3} Describes the Existence of Cycles Whose Length is a Multiple of 3.

⊧^{?} \underbrace{∃R∃G∃B∀x∃y}_{PatternE_{1}E_{1}E_{1}ae}(E(x y)∧

((R(x) ∧ ¬G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ ¬G(x) ∧ B(x))) ∧ (R(x) → G(y)) ∧ (G(x) → B(y)) ∧ (B(x) → R(y)))

((R(x) ∧ ¬G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ ¬G(x) ∧ B(x))) ∧ (R(x) → G(y)) ∧ (G(x) → B(y)) ∧ (B(x) → R(y)))

((R(x) ∧ ¬G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ ¬G(x) ∧ B(x))) ∧ (R(x) → G(y)) ∧ (G(x) → B(y)) ∧ (B(x) → R(y)))

((R(x) ∧ ¬G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ ¬G(x) ∧ B(x))) ∧ (R(x) → G(y)) ∧ (G(x) → B(y)) ∧ (B(x) → R(y)))

The Formula _{3} Describes the Existence of Cycles Whose Length is a Multiple of 3.

⊧ \underbrace{∃R∃G∃B∀x∃y}_{PatternE_{1}E_{1}E_{1}ae}(E(x y)∧

((R(x) ∧ ¬G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ ¬G(x) ∧ B(x))) ∧ (R(x) → G(y)) ∧ (G(x) → B(y)) ∧ (B(x) → R(y)))

The Formula _{3} Describes the Existence of Cycles Whose Length is a Multiple of 3.

⊧ \underbrace{∃R∃G∃B∀x∃y}_{PatternE_{1}E_{1}E_{1}ae}(E(x y)∧

((R(x) ∧ ¬G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ G(x) ∧ ¬B(x)) ∨ (¬R(x) ∧ ¬G(x) ∧ B(x))) ∧ (R(x) → G(y)) ∧ (G(x) → B(y)) ∧ (B(x) → R(y)))

Detecting Cycles Whose Length is a Multiple of 3.

Theorem There is a logspace algorithm that on input of an undirected graph G decides whether G has a cycle whose length is a multiple of 3.

Proof.

1. Check, whether G has small tree width.

2. If yes, subdivide all edges and apply the metatheorem to _{4}.

3. If no, output ‘‘yes’’.

Thomassen has shown that all graphs of sufficiently large tree width have a cycle whose length is a multiple of 3.

(A similar argument shows EVEN-CYCLE ∈ L.)

Algorithmic Metatheorems Classic Variants … … and New Variants

New Variants 1: Space Complexity New Theorems Applications: Cycle Lengths in Graphs

Applications: Quantifier Prefix Classes Applications: Integer Optimization

New Variants 2: Circuit Complexity New Theorems Applications: Visible Pushdown Languages

Formulas in Existential Second-Order Logic Describe NP.

Theorem (Fagin, 1974) A problem is in NPif, and only if, it can be described by a formula in existential second-order logic.

However, E_{1}E_{1}E_{1}aa suffices to describe NP-complete problems. What about E_{1}E_{1}E_{1}ae? What about E_{1}E_{1}aa? What about E_{1}aa? …

Can we refine Fagin’s Theorem?

Formulas in Existential Second-Order Logic Describe NP.

Theorem (Fagin, 1974) A problem is in NPif, and only if, it can be described by a formula in existential second-order logic.

However, E_{1}E_{1}E_{1}aa suffices to describe NP-complete problems. What about E_{1}E_{1}E_{1}ae? What about E_{1}E_{1}aa? What about E_{1}aa? …

Can we refine Fagin’s Theorem?

A Very Hard-To-Prove Upper Bound

Theorem (Gottlob, Kolaitis, Schwentick, 2004) E_{1}^{∗}ae formulas describe problems in Pover undirected loop-free graphs.

A Very Hard-To-Prove Upper Bound

Theorem (Gottlob, Kolaitis, Schwentick, 2004) E_{1}^{∗}ae formulas describe problems in Pover undirected loop-free graphs. Proof.

A Very Hard-To-Prove Upper Bound

Theorem (Gottlob, Kolaitis, Schwentick, 2004) E_{1}^{∗}ae formulas describe problems in Pover undirected loop-free graphs. Proof.

Original question: ⊧^{?} ∃R∃G∃B∀x∃y ( )

A Very Hard-To-Prove Upper Bound

Theorem (Gottlob, Kolaitis, Schwentick, 2004) E_{1}^{∗}ae formulas describe problems in Pover undirected loop-free graphs. Proof. New question:

Is there a special homomorphism?

\begin{matrix}⊕ \\ ⊕ \\ ⊕ \end{matrix}

A Very Hard-To-Prove Upper Bound

Theorem (Gottlob, Kolaitis, Schwentick, 2004) E_{1}^{∗}ae formulas describe problems in Pover undirected loop-free graphs. Proof.

1. Preprocess the input graph.

2. Check whether the tree width is small.

3. If so, we get a polynomial time algorithm by Courcelle’s Theorem.

4. If not, depending on the target graph,

4.1 we can either just say ‘‘yes’’ or 4.2 test whether a special cycle of constant length exists.

A Very Hard-To-Prove Upper Bound

Theorem (Gottlob, Kolaitis, Schwentick, 2004) E_{1}^{∗}ae formulas describe problems in Pover undirected loop-free graphs. Proof.

1. Preprocess the input graph.

2. Check whether the tree width is small.

3. If so, we get a polynomial time algorithm by Courcelle’s Theorem.

4. If not, depending on the target graph,

4.1 we can either just say ‘‘yes’’ or

4.2 test whether a special cycle of constant length exists.

Key Insight All steps can also be done in logspace, in particular also applying Courcelle’s Theorem because of its logspace version.

A Very Hard-To-Prove Upper Bound

Theorem (Gottlob, Kolaitis, Schwentick, 2004) E_{1}^{∗}ae formulas describe problems in Pover undirected loop-free graphs.

Theorem (T, 2015) E_{1}^{∗}ae formulas describe problems in Lover undirected loop-free graphs.

Corollary EVEN-CYCLE ∈ L.

All Pattern Classes Over Undirected Self-Loop Free Graphs

Theorem The patterns below yield the classes over undirected self-loop free graphs:

(ae)^{∗} E_{any}^{∗}e^{∗}a E_{1}aa E_{any}aa E_{1}e^{∗}aa E_{1}eaa E_{1}ae E_{1}E_{1}ae E_{2}ae E_{any}^{∗}ae E_{any}^{∗}(ae)^{∗} E_{1}E_{1}aa E_{1}aaa E_{2}eaa E_{1}eae E_{1}aee E_{1}aea E_{1}aae AC^{0} L NL NP

Till Tantau Facets of Complexity, September 2016 33/ 48

Algorithmic Metatheorems Classic Variants … … and New Variants

New Variants 1: Space Complexity New Theorems Applications: Cycle Lengths in Graphs

Applications: Quantifier Prefix Classes Applications: Integer Optimization

New Variants 2: Circuit Complexity New Theorems Applications: Visible Pushdown Languages

The Subset Sum Problem

98237534 3245 1095345 13435 39087539 759 98798754910 246301534 2336245 6245 202934435 10237 59 91111074234 The Subset Sum Problem Circle some numbers so that they add up exactly to 1000000000. This is a well-known NP-complete problem.

Till Tantau Facets of Complexity, September 2016 35/ 48

The Subset Sum Problem

98237534 3245 1095345 13435 39087539 759 98798754910 246301534 2336245 6245 202934435 10237 59 91111074234 The Subset Sum Problem Circle some numbers so that they add up exactly to 1000000000. This is a well-known NP-complete problem.

Till Tantau Facets of Complexity, September 2016 35/ 48

The Subset Sum Problem

The Unary Subset Sum Problem Circle some numbers so that they add up exactly to

.

Till Tantau Facets of Complexity, September 2016 35/ 48

The Unary Version Is In Logspace.

Theorem UNARY-SUBSET-SUM ∈ L.

Proof. For an input like , , , consider the forest

1. The size of a set S that is closed under reachability corresponds to a subset sum.

2. The formula _{closed}(X) = ∀u∀v[(X(u) ∧ E(u v)) → X(v)] describes ‘‘being closed under reachability.’’

3. New goal: Find out whether has a solution of a certain size.

The Unary Version Is In Logspace.

Theorem UNARY-SUBSET-SUM ∈ L.

Proof. For an input like , , , consider the forest

1. The size of a set S that is closed under reachability corresponds to a subset sum.

2. The formula _{closed}(X) = ∀u∀v[(X(u) ∧ E(u v)) → X(v)] describes ‘‘being closed under reachability.’’

3. New goal: Find out whether has a solution of a certain size.

A Stronger Algorithmic Metatheorem

Theorem (Elberfeld, T, Jakoby, 2010) Let (X) be an MSO formula with a free variable and let k be a number. Then there is logspace Turing machine that on input of

1. a graph G of tree width at most k and

2. a number s computes the number of subsets S with

1. |S| = s and

2. G ⊧ (S).

What We Are Really Interested In: The Original Subset Sum Problem.

Let a_{1}, …, a_{n} be the inputs and s the target sum.

Theorem Dynamic programming solves the subset sum problem in time O(ns) and

space O(s).

For larger s, space is the bottleneck: 4GB of memory are filled in one second for s = 1 000 000 000.

Unknown author, Creative Commons Attribution Sharealike License

A Magic Trick.

Real input 2;9;5;20 Virtual input (read only)

11;111111111;11111;11111111111111111111 Work tape 42

Virtual logspace machine M Real machine

Till Tantau Facets of Complexity, September 2016 39/ 48

A Magic Trick.

A similar argument shows that there are space efficient pseudo-polynomial time algorithms for:

knapsack problems, bin packing problems, scheduling problems, and integer programming for a fixed number of inequalities.

Algorithmic Metatheorems Classic Variants … … and New Variants

New Variants 1: Space Complexity New Theorems Applications: Cycle Lengths in Graphs

Applications: Quantifier Prefix Classes Applications: Integer Optimization

New Variants 2: Circuit Complexity New Theorems Applications: Visible Pushdown Languages

The Class NC^{1}

NC^{1}

\begin{matrix}y_{1} \\ ∧ \\ fan in 2 \\ ∧ \\ ∨ \\ ∨ \\ ∧ \\ ∨ \\ ∨ \\ ∧ \\ ∨ \\ ∧ \\ ∨ \end{matrix}

x_{1} x_{2} x_{3} x_{4} x_{5} x_{6} x_{7} x_{8}

n input gates log n layers

REG⊆ NC^{1} ⊆ L. Addition, multiplication, and division all lie in NC^{1}. Tree decompositions cannot be computed in NC^{1} unless NC^{1} = L.

The NC^{1} Version of Courcelle’s Theorem.

Theorem (Elberfeld, T, Jakoby, 2012) Let be an MSO formula and k a number. Then there is an NC^{1} circuit family that on input of

1. a graph G

2. together with a tree decomposition of G of width k decides whether G ⊧ .

(As for logspace, there is also a ‘‘counting version’’.)

Algorithmic Metatheorems Classic Variants … … and New Variants

New Variants 1: Space Complexity New Theorems Applications: Cycle Lengths in Graphs

Applications: Quantifier Prefix Classes Applications: Integer Optimization

New Variants 2: Circuit Complexity New Theorems Applications: Visible Pushdown Languages

Visible Pushdown Languages

1. The input is processed by a pushdown automaton.

2. Whether the automaton does a push or a pop may depend only

on the read symbol and not on the state.

Input tape ( [ 1 + 1 ] + ( 2 + [ 2 + 2 ] ) ) Stack ( ( [ ( [ ( [ ( [ ( ( ( ( ( ( ( ( ( ( [ ( ( [ ( ( [ ( ( [ ( ( (

We Can Precompute the Stack Outline

1. The input is processed by a pushdown automaton.

2. Whether the automaton does a push or a pop may depend only

on the read symbol and not on the state.

Input tape ; ↑ ; ↑ ; ↓ ; ↑ ; ↑ ; ↓ ; ↓ ; ↓ ; Stack

The Complexity of Visible Pushdown Languages

Theorem All visible pushdown languages lie in NC^{1}.

Proof. For an input like ([1 + 1] + (2 + [2 + 2])) we can construct the following graph using ‘‘simple counting’’:

Apply the metatheorem for NC^{1} to a formula stating ‘‘there exist states and symbols for the nodes that are locally consistent’’.

The Complexity of Visible Pushdown Languages

Theorem All visible pushdown languages lie in NC^{1}.

Proof. For an input like ([1 + 1] + (2 + [2 + 2])) we can construct the following graph using ‘‘simple counting’’:

Apply the metatheorem for NC^{1} to a formula stating ‘‘there exist states and symbols for the nodes that are locally consistent’’.

Summary

Algorithmic metatheorems have the form If a problem can be described in a certain logic and the input graphs can be decomposed in a certain fashion, then there is a certain kind of algorithm.

There are algorithmic metatheorems for logarithmic space. There are algorithmic metatheorems for NC^{1}. Algorithmic metatheorems have applications even when the inputs are not decomposable graphs.

Outlook

Further Results There are algorithmic metatheorems for constant depth circuits (AC_{0} and TC_{0}).

There are algorithmic metatheorems for pure logic.

Some Open Problems Is there an logspace metatheorem for bounded clique width?

Can we construct solutions of a certain size?

How difficult is detecting cycles whose length modulo 3 is 1?