2 problems

0 votes0 replies0 views
FL-completeness conjecture for the median genome rearrangement problem
FL-completeness conjecture. Our bound is optimal: $\textsc{\#Median}$ is $\textsf{FL}$ -complete.
Conjectureopencomputational-complexity enumeration genome-rearrangementarXiv posted 2 days ago
0 votes0 replies1 view
The 3n/4 upper-bound conjecture for prefix transposition sorting
Let a permutation with $n$ symbols be given. A prefix transposition moves a prefix of the permutation to a later position while preserving the order of the moved symbols and the re…
Conjecturesolvedgenome-rearrangement permutation-sorting prefix-transpositionsarXiv posted 2 days ago

FL-completeness conjecture for the median genome rearrangement problem