Seminár z teoretickej informatiky - Rastislav Královič (5.10.2018)

v piatok 5.10.2018 o 11:00 hod. v miestnosti M/213

02. 10. 2018 14.45 hod.
Od: Rastislav Královič

Prednášajúci: Rastislav Královič

Názov: The complexity of thinning

Termín: 5.10.2018, 11:00 hod., M/213

Abstrakt:
Jazyk sa nazýva k-riedky, ak pre každé n obsahuje najviac k slov dĺžky n. Riedke jazyky sa vynárajú na rôznych miestach v teórii jazykov aj v teórii zložitosti (napr. existencia nekonečných riedkych podmnožín súvisí s existenciou istých hešovacích funkcií). V literatúre existuje niekoľko operácií "zrieďovania" jazykov: napr. decimácia, kde sa z jazyka (v utriedení primárne podľa dĺžky a potom lexikograficky) vyberie každé k-te slovo, alebo minimalizácia, kde sa z jazyka vyberie lexikograficky prvých k slov danej dĺžky. Je napr. známe, že min(P) je podmnožinou coNP a min(NP) je podmnožinou DP. Zaujímavá je opačná otázka: napr. či min(NP) môže obsahovať jazyk úplný pre DP (resp. pre triedu riedkych DP jazykov). Túto otázku síce zodpovedať nevieme, ale ukážeme slabší výsledok: existuje relativizovaný svet, v ktorom existuje k-riedky NP jazyk, ktorý sa nedá polynomiálne redukovať na žiaden (k-1)-riedky NP jazyk. Podobný výsledok platí nielen pre triedu NP, ale pre všetky "dostatočne bohaté" triedy.

web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php