<p>It depends a bit on what kind of problems you're looking at, but the path systems problem may be a candidate.</p>

<p>Given: A finite set of propositions $P$, a set $A \subseteq P$ of axioms, a set $R \subseteq P \times P \times P$ of inference rules and some target $p \in P$.</p>

<p>Question: Is $p$ provable from $A$ using $R$? </p>

<p>Here, every proposition in $A$ is provable from $A$ using $R$ and, if there's a rule $(p_1,p_2,p_3)$ in $R$ and $p_1$ and $p_2$ are provable from $A$ using $R$, then also $p_3$ is provable from $A$ using $R$.</p>

<p>The point is that the structure of such a proof is a tree.</p>

<p>A closely related problem is the language emptiness problem for a context-free grammar: Given a context-free grammar, does it have at least one derivation tree?  (The reduction from path systems is almost immediate.) Therefore, language emptiness of context-free grammars is P-complete.
Due to a very similar reason, the emptiness problem for tree automata is also P-complete.</p>

<p>A reference on path systems is: 
Stephen Cook: An Observation on Time-Space storage trade-off. JCSS, 1974.</p>

CC BY-SA 3.0
2011-11-11T11:13:32.590Z
2011-11-11T11:13:32.590Z
Wim Martens
<p>I'd like to suggest some possible candidates for P-completeness:</p>

<ul>
<li>the Generalized Pebbling Game for trees (see "An Application of Generalized Tree Pebbling to Sparse Matrix Factorization" by J.W.H. Liu)</li>
<li>The Agreement Supertree problem in phylogenetics (see "Fixed-Parameter Algorithms for Agreement Supertrees" by D. Fernandez-Baca et al).</li>
</ul>

<p>The P-completeness is not clear to me though, a reduction from HornSAT seems possible but tricky; maybe the Target Set Selection problem would be a more natural starting point?</p>

CC BY-SA 3.0
2014-02-20T16:16:29.897Z
On a related note, I think that the P-completeness of the second problem follows from "Resolving Rooted Triplet Inconsistency by Dissolving Multigraphs" by Chester et al. I'm not sure about the first one though.
NisaiVloot
CC BY-SA 3.0
2014-02-21T09:52:28.843Z
Also, I have an idea for a third problem involving colored BSP trees, but I have to figure out the precise definition. Stay tuned...
NisaiVloot
CC BY-SA 3.0
2014-04-24T19:47:26.550Z
Your update in a separate answer to this answer should be a comment or an edit.  Hence, I have deleted it.
Lev Reyzin
CC BY-SA 3.0
2014-04-24T22:07:13.037Z
I posted a separate answer to have it appear in the question stream, so let me repeat: the first problem 'Generalized Pebbling Game for trees' is probably NOT $\sf{P}$-complete as it seems solvable in $O(\log^2 n)$ space, at least in its current definition. Also, for the second problem it's a matter of interpretation whether it answers the question or not -- technically it involves a 'tree profile' rather than a 'tree'.
Super8
CC BY-SA 3.0
2014-02-20T11:18:35.157Z
2014-02-20T11:18:35.157Z
NisaiVloot
<p>Here is the third problem I mentioned, called Quad Tree Recoloring. We are given:</p>

<ul>
<li>a matrix of colors $\Gamma = (\gamma_{i,j})$,</li>
<li>a quad-tree $T$ whose leaves are labelled by elements of $\Gamma$,</li>
</ul>

<p>and the goal is to recolor the minimum number of nodes of $T$ such that no two adjacent nodes of $T$ are labelled by colors adjacent in $\Gamma$.</p>

<p>Another possible cost function would be to count the <em>surface</em> of recolored nodes instead of their number. I conjecture that this problem is P-complete, but even membership in P is not immediate.</p>

CC BY-SA 3.0
2014-04-25T01:46:46.533Z
Why is this a "third problem"?  Is this an addition to another answer?
Lev Reyzin
CC BY-SA 3.0
2014-04-25T02:57:30.360Z
And why can't you combine it with your other answer ?
Suresh Venkat
CC BY-SA 3.0
2014-04-25T03:31:53.337Z
Yes, this was an addition to the answer above; given the recent update this should be considered as a 'second problem' on my side. This problem was just a 'guesstimate' based on practical considerations, I'm still unsure about the membership in P; maybe considering alternative topologies such as hexagonal tilings could change the complexity? I'll keep looking for other candidates and I'll merge the answers eventually - assuming that I can access to the old 'Super8' profiles created 2 months ago.
Super8
CC BY-SA 3.0
2014-04-25T13:17:00.887Z
Using multiple profiles this way creates clutter and more work for mods. This is a shared resource, and it's upto all of us to keep things "tidy".
Suresh Venkat
CC BY-SA 3.0
2014-02-21T20:54:16.663Z
2014-02-21T20:54:16.663Z
Super8
<p>A recent one, presented at ICALP is</p>

<p>Markus Lohrey, Christian Mathissen: Isomorphism of Regular Trees and Words. ICALP (2) 2011: 210-221</p>

<p>You will find the paper both on <a href="http://arxiv.org/abs/1102.2782">arxiv</a>
and <a href="http://www.informatik.uni-leipzig.de/~lohrey/11-ICALP.pdf">here</a>.</p>

<p>Another example is  Mostowski epimorphism (see P-completeness and efficient parallelization by Satoru Miyano, and the paper by <a href="http://www.springerlink.com/content/p854k0076nm51437/">Dahlhaus</a>): </p>

<p>Dahlhaus E, Is SETL a suitable language for parallel programming - a theoretical approach, Computer science logic, 1st Workshop, CSL ’87, Karlsruhe/FRG 1987, Lect. Notes Comput. Sci. 329, 56-63, 1988)</p>

<p>Instance: a directed acyclic graph $D = (V, A)$ satisfying the axiom of extensionality and two vertices $x_1, x_2 \in V$ </p>

<p>Problem: Decide whether $M_D(x_1) = M_D(x_2)$, where $M_D$ is the Mostowski epimorphism for $D$.</p>

CC BY-SA 3.0
2011-11-10T07:29:30.427Z
2011-11-10T07:29:30.427Z
Massimo Cafaro
<p>This question is related to one of my previous questions, <a href="https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees">NP-hard problems on trees</a>.</p>

<blockquote>
  <p>I am looking for problems that are P-complete on trees.</p>
</blockquote>

CC BY-SA 3.0
2011-11-09T16:41:23.510Z
Some motivation might help.
Suresh Venkat
CC BY-SA 3.0
2011-11-09T16:46:39.147Z
I would like to use such a problem in proving hardness of some problems on bounded tree width graphs.
Shiva Kintali
CC BY-SA 3.0
2014-04-25T01:39:40.133Z
The bible, https://homes.cs.washington.edu/~ruzzo/papers/limits.pdf
Chad Brewbaker
<cc.complexity-theory><graph-theory><tree><p-hardness>
P-complete problems on trees
Shiva Kintali
# P-complete problems on trees

(Asked by: username_0 on 2011-11-09)

This question is related to one of my previous questions, [NP-hard problems on trees](https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees).

> I am looking for problems that are P-complete on trees.

**Tags:** cc.complexity-theory, graph-theory, tree, p-hardness
> **Comments:**
> **username_1**: Some motivation might help.  
> **username_0**: I would like to use such a problem in proving hardness of some problems on bounded tree width graphs.  
> **username_2**: The bible, https://homes.cs.washington.edu/~ruzzo/papers/limits.pdf  

---

## 4 answers

### Answer by username_7 on 2011-11-10. Score: 11 | Accepted answer

A recent one, presented at ICALP is

Markus Lohrey, Christian Mathissen: Isomorphism of Regular Trees and Words. ICALP (2) 2011: 210-221

You will find the paper both on [arxiv](http://arxiv.org/abs/1102.2782)
and [here](http://www.informatik.uni-leipzig.de/~lohrey/11-ICALP.pdf).

Another example is Mostowski epimorphism (see P-completeness and efficient parallelization by Satoru Miyano, and the paper by [Dahlhaus](http://www.springerlink.com/content/p854k0076nm51437/)):

Dahlhaus E, Is SETL a suitable language for parallel programming - a theoretical approach, Computer science logic, 1st Workshop, CSL ’87, Karlsruhe/FRG 1987, Lect. Notes Comput. Sci. 329, 56-63, 1988)

Instance: a directed acyclic graph $D = (V, A)$ satisfying the axiom of extensionality and two vertices $x\_1, x\_2 \in V$

Problem: Decide whether $M\_D(x\_1) = M\_D(x\_2)$, where $M\_D$ is the Mostowski epimorphism for $D$.


---

### Answer by username_3 on 2011-11-11. Score: 6

It depends a bit on what kind of problems you're looking at, but the path systems problem may be a candidate.

Given: A finite set of propositions $P$, a set $A \subseteq P$ of axioms, a set $R \subseteq P \times P \times P$ of inference rules and some target $p \in P$.

Question: Is $p$ provable from $A$ using $R$?

Here, every proposition in $A$ is provable from $A$ using $R$ and, if there's a rule $(p\_1,p\_2,p\_3)$ in $R$ and $p\_1$ and $p\_2$ are provable from $A$ using $R$, then also $p\_3$ is provable from $A$ using $R$.

The point is that the structure of such a proof is a tree.

A closely related problem is the language emptiness problem for a context-free grammar: Given a context-free grammar, does it have at least one derivation tree? (The reduction from path systems is almost immediate.) Therefore, language emptiness of context-free grammars is P-complete.
Due to a very similar reason, the emptiness problem for tree automata is also P-complete.

A reference on path systems is:
Stephen Cook: An Observation on Time-Space storage trade-off. JCSS, 1974.


---

### Answer by username_4 on 2014-02-20. Score: 1

I'd like to suggest some possible candidates for P-completeness:

* the Generalized Pebbling Game for trees (see "An Application of Generalized Tree Pebbling to Sparse Matrix Factorization" by J.W.H. Liu)
* The Agreement Supertree problem in phylogenetics (see "Fixed-Parameter Algorithms for Agreement Supertrees" by D. Fernandez-Baca et al).

The P-completeness is not clear to me though, a reduction from HornSAT seems possible but tricky; maybe the Target Set Selection problem would be a more natural starting point?

> **Comments:**
> **username_4**: On a related note, I think that the P-completeness of the second problem follows from "Resolving Rooted Triplet Inconsistency by Dissolving Multigraphs" by Chester et al. I'm not sure about the first one though.  
> **username_4**: Also, I have an idea for a third problem involving colored BSP trees, but I have to figure out the precise definition. Stay tuned...  
> **username_5**: Your update in a separate answer to this answer should be a comment or an edit.  Hence, I have deleted it.  
> **username_6**: I posted a separate answer to have it appear in the question stream, so let me repeat: the first problem 'Generalized Pebbling Game for trees' is probably NOT $\sf{P}$-complete as it seems solvable in $O(\log^2 n)$ space, at least in its current definition. Also, for the second problem it's a matter of interpretation whether it answers the question or not -- technically it involves a 'tree profile' rather than a 'tree'.  

---

### Answer by username_6 on 2014-02-21. Score: 1

Here is the third problem I mentioned, called Quad Tree Recoloring. We are given:

* a matrix of colors $\Gamma = (\gamma\_{i,j})$,
* a quad-tree $T$ whose leaves are labelled by elements of $\Gamma$,

and the goal is to recolor the minimum number of nodes of $T$ such that no two adjacent nodes of $T$ are labelled by colors adjacent in $\Gamma$.

Another possible cost function would be to count the *surface* of recolored nodes instead of their number. I conjecture that this problem is P-complete, but even membership in P is not immediate.

> **Comments:**
> **username_5**: Why is this a "third problem"?  Is this an addition to another answer?  
> **username_1**: And why can't you combine it with your other answer ?  
> **username_6**: Yes, this was an addition to the answer above; given the recent update this should be considered as a 'second problem' on my side. This problem was just a 'guesstimate' based on practical considerations, I'm still unsure about the membership in P; maybe considering alternative topologies such as hexagonal tilings could change the complexity? I'll keep looking for other candidates and I'll merge the answers eventually - assuming that I can access to the old 'Super8' profiles created 2 months ago.  
> **username_1**: Using multiple profiles this way creates clutter and more work for mods. This is a shared resource, and it's upto all of us to keep things "tidy".  

---

