Counting complexity of partion functions over optimal medians / Optimális mediánokon értelmezett partíciófüggvények

Type: 
Lecture
Audience: 
Open to the Public
Thursday, March 12, 2015 - 2:15pm
Add to Calendar
Date: 
Thursday, March 12, 2015 - 2:15pm

This lecture can be held in English, if it is needed.

Venue: MTA Rényi Intézet, nagyterem, Budapest, Reáltanoda Street, Hungary

Legyen $\mathcal{S}$ véges, azonos hosszú, $\{0,1 \}$ ABC feletti szekvenciáknak egy véges halmaza, és $\mathcal{M}$ az optimális mediánjaik halmaza, azaz azon $M$ szekvenciák, amelyek minimalizálják az $\mathcal{S}$-beli szekvenciáktól vett Hamming távolságok összegét. Legyen $f$ a nemnegatív egészekről nemnegatív számokra képező monoton függvény, amely szerinti partíciófüggvényét $\mathcal{M}$-nek definiáljuk úgy, hogy $$Z(\mathcal{M}) := \sum_{M \in \mathcal{M}} \prod_{S \in \mathcal{S}} f\left(|S \Delta M | \right) $$ Vizsgálatunk központi tárgya az, hogy milyen $f$ függvényekre lesz a partíciófüggvény kiszámolása könnyű, azaz van olyan számolás, amelyben a szükséges operációk száma mind $\mathcal{S}$ méretével, mind a $\mathcal{S}$-ben levő szekvenciák hosszával polinomiálisan növekszik. A gyakorlatban a legfontosabb eset az, amikor $f$ a faktoriális függvény, ekkor a partíciófüggvény a minimális méretű történetek számát adja meg abban a csillag alakú fában, amelynek a levelei az $\mathcal{S}$-beli szekvenciákkal vannak felcimkézve, egy minimális méretű történet pedig a csillag centrumának egy $\mathcal{M}$-beli szekvenciával való felcimkézése, a csillag élein pedig annak a megadása, hogy a medián szekvenciából a levélhez rendelt szekvenciát a szükséges $0 \rightarrow 1$ és $1 \rightarrow 0$ változtatások milyen sorrendjével kaptuk meg. A fő eredményünk az, hogy a faktoriális függvény szerinti partíciófüggvény kiszámolása \#P-teljes. Nyitott kérdés, hogy létezik-e FPRAS közelítés (és mivel a feladat önhasonló, ekvivalensen, létezik-e gyors, közel egyenletes mintavételezése a minimális méretű történeteknek), vagy ilyen közelítések és mintavételezések létezéséből következne-e, hogy RP = NP. Közös munka Heather Smith-szel.