Counting consistent phylogenetic trees is \#P-complete (Q1883389)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Counting consistent phylogenetic trees is \#P-complete |
scientific article; zbMATH DE number 2107235
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Counting consistent phylogenetic trees is \#P-complete |
scientific article; zbMATH DE number 2107235 |
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
0.9625456
0 references
0.89512336
0 references
0.8713686
0 references
0.8685641
0 references
0.8588343
0 references
0.85664195
0 references
0.85601014
0 references
0 references
