|
|
NP vyhledávací problémy a redukce mezi nimi
Ševčíková, Renáta ; Krajíček, Jan (vedoucí práce) ; Pudlák, Pavel (oponent)
NP vyhledávací problémy a redukce mezi nimi Renáta Ševčíková V předložené práci studujeme třídu Total NP vyhledávacích problémů. Větší pozornost je věnována studiu podtříd této třídy a redukcí mezi nimi. Kombinujeme známé metody: vyhledávací stromy a jejich vztah k redukcím, důkaz sporem pomocí Nullstellensatz důkazového systému a dolní odhad na stupeň tohoto důkazu pomocí designů, abychom ukázali, že dvě třídy relativi- zovaných NP vyhledávacích problémů založených na Mod-p počítacím principu a Mod-q počítacím principu, kde p a q jsou různá prvočísla, nejsou mezi sebou redukovatelné. Práce je ukončena novým výsledkem separace pro p = 2 a q = 3.
|
|
| |
|
|
NP vyhledávací problémy a redukce mezi nimi
Ševčíková, Renáta ; Krajíček, Jan (vedoucí práce) ; Pudlák, Pavel (oponent)
NP vyhledávací problémy a redukce mezi nimi Renáta Ševčíková V předložené práci studujeme třídu Total NP vyhledávacích problémů. Větší pozornost je věnována studiu podtříd této třídy a redukcí mezi nimi. Kombinujeme známé metody: vyhledávací stromy a jejich vztah k redukcím, důkaz sporem pomocí Nullstellensatz důkazového systému a dolní odhad na stupeň tohoto důkazu pomocí designů, abychom ukázali, že dvě třídy relativi- zovaných NP vyhledávacích problémů založených na Mod-p počítacím principu a Mod-q počítacím principu, kde p a q jsou různá prvočísla, nejsou mezi sebou redukovatelné. Práce je ukončena novým výsledkem separace pro p = 2 a q = 3.
|
|
| |
host ::
RSS.