Prostorska zahtevnost grafovskih dominacijskih igerRAJTER, MIHA (Avtor) Raič, Martin (Mentor) Dominacijske igre na grahIgralno dominacijsko številoČasovna zahtevnostProstorska zahtevnostTuringovi strojiPSPACE-polnostPOS-CNF problem.V nalogi obravnavamo dominacijske igre na grah, njihove različice in igralno dominacijsko število, ki je število potez v poteku dominacijske igre, v kateri oba igralca igrata optimalno. Ukvarjamo se s prostorsko zahtev- nostjo izračuna igralnega dominacijskega števila. Pokažemo, da je igralno dominacijsko število možno izračunati z algoritmom, ki ima linearno pro- storsko zahtevnost, kar pomeni, da je problem v razredu PSPACE. Končno dokažemo, da je problem dominacijskih iger na grah PSPACE-poln za pre- vedbe v polinomskem času. To storimo s sklicevanjem na PSPACE-polnost problema zmagovalca igre na izjavnih formulah v konjuktivni obliki brez ne- gacij (POS-CNF).20212021-10-13 12:05:05Diplomsko delo/naloga132122sl