Nemdeterminisztikus tulajdonság-tesztelés gráfokon
<br><br>
Vesztergombi Katalin
<br><br>
Véges gráfok egy tulajdonságát akkor nevezzük nemdeterminisztikusan
tesztelhet&#337;nek, ha van olyan "tanusítványa", amit ha megadunk, akkor
véletlen lokális teszteléssel ellen&#337;rizhet&#337; a tanusítvány
helyessége. Ebben az el&#337;adásban s&#369;r&#369; gráfokat vizsgálunk,
és olyan tanusítványokat engedünk meg, melyek egy vagy több unáris és
bináris relációból állnak. A gráflimesz-elméletet használva bebizonyítjuk,
hogy minden nemdeterminisztikusan tesztelhet&#337; tulajdonság
determinisztikusan is tesztelhet&#337;. (Röviden: s&#369;r&#369; gráfokra
P=NP.) Közös munka Lovász Lászlóval.