<p>This problem is highly related to the <a href="https://cstheory.stackexchange.com/questions/3059/the-complexity-of-checking-whether-two-cnf-have-the-same-number-of-solutions">CNF</a> one.</p>

<p>Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No".</p>

<p>Intuitively, the complexity of this problem is <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:C#cequalsp" rel="noreferrer">$C_=P$</a>-complete, just as the <a href="https://cstheory.stackexchange.com/questions/3059/the-complexity-of-checking-whether-two-cnf-have-the-same-number-of-solutions">CNF</a> one. It is easy to see it is in $C_=P$, but is it $C_=P$-hard?</p>

CC BY-SA 2.5
2010-11-17T22:34:12.757Z
@Mike Chen Could you, please, explain what is $C_=P$? And what do you mean by the "counting of topological sorts"?
Oleksandr Bondarenko
CC BY-SA 2.5
2010-11-17T22:44:10.470Z
@Oleksandr: I added a link to $C_=P$ in the question. "counting of topological sorts" means the number of topological sorts.
Mike Chen
CC BY-SA 2.5
2010-11-17T22:47:53.260Z
@Mike Chen As I understood by the "counting of topological sorts" you mean the number of linear extensions of a given partial order, don't you? According to http://scholar.google.com/scholar?hl=en&q=intitle:%22Counting++Linear++Extensions%22&btnG=Search&as_sdt=2001&as_ylo=&as_vis=0 the problem of counting the number of linear extensions of a partially ordered set is $\sharp P$-complete.
Oleksandr Bondarenko
CC BY-SA 2.5
2010-11-17T22:58:12.470Z
@Mike Chen Thank you for clarification on $C_=P$! Intuitively, your problem is not easier than the counting of linear extensions.
Oleksandr Bondarenko
CC BY-SA 2.5
2010-11-17T22:59:14.413Z
Right, the counting version of this problem is $\#P$-complete. But what I really wanna know is if counting of solutions is $\#P$-complete, is the problem of deciding whether two have the same number of solutions $C_=P$-complete?
Mike Chen
CC BY-SA 2.5
2010-12-02T04:42:37.553Z
You probably already know this, but let me write this down for others: this problem is not (apparently) the same as the other question on [deciding whether two CNF formulas have the same number of solutions](http://cstheory.stackexchange.com/q/3059).  The reason is that counting the solutions to a given CNF formula is #P-complete _under parsimonious reductions_ whereas counting the topological sorts of a given DAG is not (unless P=NP).  Counting the topological sorts is #P-complete only under functional reductions between counting problems (also called weakly parsimonious reductions).
Tsuyoshi Ito
CC BY-SA 3.0
2014-05-16T22:28:52.580Z
This is loosely related to http://math.stackexchange.com/q/793098 in the following sense: if you can answer this last question in the positive, then it should be hard to decide whether an input poset $P$ has *more* or *less* linear extensions than an input poset $P'$, as you can do a binary search to count linear extensions using an algorithm for this last problem and an algorithm to build posets with known number of linear extensions. (OK, deciding *less* or *more* is still not the same as deciding if the number is *exactly* equal.)
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2016-02-08T23:34:30.940Z
Somewhat related: Deciding whether two unweighted graphs have the same number of perfect matchings is C=P-complete. Like in your problem, the counting problem here is also not #P-complete under parsimonious reductions. http://arxiv.org/abs/1511.07480
Radu Curticapean
CC BY-SA 4.0
2022-03-26T21:34:43.530Z
The C=P is now broken and was probably moved to https://complexityzoo.net/Complexity_Zoo:C#:~:text=C%3DP%3A%20Exact%2DCounting,coNQP%20%5BFGH%2B98%5D.
Albert Hendriks
<cc.complexity-theory><complexity-classes><counting-complexity><open-problem><partial-order>
The complexity of checking whether two DAG have the same number of topological sorts
Mike Chen
# The complexity of checking whether two DAG have the same number of topological sorts

(Asked by: username_0 on 2010-11-17)

This problem is highly related to the [CNF](https://cstheory.stackexchange.com/questions/3059/the-complexity-of-checking-whether-two-cnf-have-the-same-number-of-solutions) one.

Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No".

Intuitively, the complexity of this problem is [$C\_=P$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:C#cequalsp)-complete, just as the [CNF](https://cstheory.stackexchange.com/questions/3059/the-complexity-of-checking-whether-two-cnf-have-the-same-number-of-solutions) one. It is easy to see it is in $C\_=P$, but is it $C\_=P$-hard?

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity, open-problem, partial-order

> **Comments:**
> **username_1**: @username_0 Could you, please, explain what is $C_=P$? And what do you mean by the "counting of topological sorts"?  
> **username_0**: @Oleksandr: I added a link to $C_=P$ in the question. "counting of topological sorts" means the number of topological sorts.  
> **username_1**: @username_0 As I understood by the "counting of topological sorts" you mean the number of linear extensions of a given partial order, don't you? According to http://scholar.google.com/scholar?hl=en&q=intitle:%22Counting++Linear++Extensions%22&btnG=Search&as_sdt=2001&as_ylo=&as_vis=0 the problem of counting the number of linear extensions of a partially ordered set is $\sharp P$-complete.  
> **username_1**: @username_0 Thank you for clarification on $C_=P$! Intuitively, your problem is not easier than the counting of linear extensions.  
> **username_0**: Right, the counting version of this problem is $\#P$-complete. But what I really wanna know is if counting of solutions is $\#P$-complete, is the problem of deciding whether two have the same number of solutions $C_=P$-complete?  
> **username_2**: You probably already know this, but let me write this down for others: this problem is not (apparently) the same as the other question on [deciding whether two CNF formulas have the same number of solutions](http://cstheory.stackexchange.com/q/3059).  The reason is that counting the solutions to a given CNF formula is #P-complete _under parsimonious reductions_ whereas counting the topological sorts of a given DAG is not (unless P=NP).  Counting the topological sorts is #P-complete only under functional reductions between counting problems (also called weakly parsimonious reductions).  
> **username_3**: This is loosely related to http://math.stackexchange.com/q/793098 in the following sense: if you can answer this last question in the positive, then it should be hard to decide whether an input poset $P$ has *more* or *less* linear extensions than an input poset $P'$, as you can do a binary search to count linear extensions using an algorithm for this last problem and an algorithm to build posets with known number of linear extensions. (OK, deciding *less* or *more* is still not the same as deciding if the number is *exactly* equal.)  
> **username_4**: Somewhat related: Deciding whether two unweighted graphs have the same number of perfect matchings is C=P-complete. Like in your problem, the counting problem here is also not #P-complete under parsimonious reductions. http://arxiv.org/abs/1511.07480  
> **username_5**: The C=P is now broken and was probably moved to https://complexityzoo.net/Complexity_Zoo:C#:~:text=C%3DP%3A%20Exact%2DCounting,coNQP%20%5BFGH%2B98%5D.  

---

## 0 answers

