Counting consistent phylogenetic trees is \#P-complete (Q1883389)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Counting consistent phylogenetic trees is \#P-complete |
scientific article |
Statements
Counting consistent phylogenetic trees is \#P-complete (English)
0 references
12 October 2004
0 references
The paper studies the complexity of counting rooted phylogenetic (super)trees consistent to a set of (possibly overlapping) rooted phylogenetic trees, and shows that it (similarly to two other related problems) is \#P-complete. The proof works through reducing the problem \(\#\)-\texttt{MON-2-SAT} to the problem at hand.
0 references
\#P complete counting
0 references
NP-complete decision problem
0 references
\(\#\)-\texttt{MON-2-SAT} problem
0 references
0 references
