30

This problem is highly related to the CNF 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$-complete, just as the CNF one. It is easy to see it is in $C_=P$, but is it $C_=P$-hard?

Community
  • 1
Mike Chen
  • 709
  • 4
  • 10
  • @Mike Chen Could you, please, explain what is $C_=P$? And what do you mean by the "counting of topological sorts"? – Oleksandr Bondarenko Nov 17 '10 at 22:34
  • @Oleksandr: I added a link to $C_=P$ in the question. "counting of topological sorts" means the number of topological sorts. – Mike Chen Nov 17 '10 at 22:44
  • @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 Nov 17 '10 at 22:47
  • @Mike Chen Thank you for clarification on $C_=P$! Intuitively, your problem is not easier than the counting of linear extensions. – Oleksandr Bondarenko Nov 17 '10 at 22:58
  • 2
    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 Nov 17 '10 at 22:59
  • 4
    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. 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 Dec 02 '10 at 04:42
  • 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.) – a3nm May 16 '14 at 22:28
  • 2
    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 Feb 08 '16 at 23:34
  • 1
    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 Mar 26 '22 at 21:34

0 Answers0