A #P osztályba függvényproblémák tartoznak, mégpedig azok az f, szavakhoz természetes számot rendelő függvények, melyekhez létezik olyan nemdeterminisztikus polinomidejű M, Turing-gép, hogy tetszőleges x-re f(x) épp az elfogadó utak száma, ha M-et x-en futtatjuk.
Nyilván minden NP-beli nyelv karakterisztikus függvénye megkapható mint egy #P-beli függvény szignuma, így #P elég nehéz problémákat is tartalmazhat; másfelől persze mivel egy NP gép összes számolását polinom tárban el tudjuk determinisztikusan is végezni, a #P-beli függvények mind FPSPACE-ben vannak.
Vannak persze #P-teljes problémák is; az ember nem lepődik meg azon, hogy pl. a #SAT (input CNF-nek hány kielégítő kiértékelése van) egy #P-teljes probléma (ezt be is látjuk melegítésként). Az már inkább meglepő, hogy vannak könnyű problémák, melyek "számolós" változata #P-teljes: erről szól pl. Valiant '79-es eredménye (input páros gráfban MENNYI maximális párosítás van?), vagy a 2-SAT számolós változata; előbbinek az eldöntési változata RNC-be esik (de nem ismert, hogy bármelyik "természetes" osztályban teljes lenne), utóbbi NL-teljes, tehát ezek bőven polinomidőben megoldható problémák.
Az előadásban ezekről fogok beszélni; ha minden igaz, Valiant eredményének egy 2011-es keletű, kvantumszámításos bizonyítását fogom vázlatosan ismertetni, persze úgy, hogy mindent, ami kellhet, definiálok és kimondok, nem kell hozzá előismeret.
Minden érdeklődőt szeretettel várunk,
Péter