Miklos Istvan:
A legtakarékosabb szimpla vágás vagy kötés utak számáról
<br><br>
Absztrakt:
A szimpla vágás vagy kötés (Single Cut or Join, SCoJ) komputációsan a
lehet? legegyszer?bb genomátrendez?dési modell, amelyet Feijao és Meidanis
vezetett be egy évvel ezel?tt. Megmutatták, hogy polinom futási idej?
algoritmus létezik két genom közötti legtakarékosabb átrendezési út
megtalálására, s?t, az úgynevezett kis parszimónia probléma is polinom
id?ben megmutatható. Minden más publikált modellre a kis parszimónia
probléma bizonyítottan NP-nehéz.
<br><br>

Az el?adáson röviden ismertetem az eredményeiket, és utána arról fogok
beszélni, hogy hány legtakarékosabb SCoJ út létezik két genom között,
illetve hány legtakarékosabb evolúciós történet van a kis parszimónia
problémára. Megmutatjuk, hogy a két genom közötti legtakarékosabb utak
leszámolási problémája FP-ben van, azaz polinom id?ben meg lehet mondani az
utak pontos számát, valamint ezen utak száma az alternáló permutációk
számával, azaz a tangens és szekáns számokkal
(A000182<http://oeis.org/A000182>
 és A000364 <http://oeis.org/A000364>) van kapcsolatban.


<br><br>
A kis parszimónia probléma megoldásait adó legtakarékosabb evolúciós
történetek leszámolási problémája azonban nehéz: megmutatjuk, hogy ha ez a
probléma FP-ben lenne, akkor abból adódna az, hogy P = NP (amiben nem
hiszünk), illetve ha lenne ezen leszámolási problémára FPRAS (Fully
Polynomial Randomized Approximation Scheme), akkor abból következne, hogy
RP = NP (amiben szintén nem hiszünk).