A csúcsokon adott egy irányított gráf. Tegyük fel, hogy .

Az alábbi feladatok közül melyiket NEM lehet polinomiális időben megoldani tetszőleges gráf esetén?

Milyen hiba ellen nem véd a szigorú 2PL (kétfázisú zárolás) protokoll?

Adott egy G→H funkcionális függés. Ekkor

Egy három egyedet tartalmazó A egyedhalmaz és egy két egyedet tartalmazó B egyedhalmaz közötti egy-egy kardinalitású kapcsolathalmaznak legfeljebb hány eleme lehet?

Az eldöntési problémáról annyit tudunk, hogy -ben van, az eldöntési problémáról pedig annyit, hogy -teljes.

Mi igaz az alábbiak közül, ha feltételezzük, hogy ?

Tekintsük a következő eldöntési problémát: 

Adott egy csúcsú egyszerű gráf, amiről azt kell eldönteni, hogy kiszínezhetők-e a csúcsai 2026 színnel úgy, hogy azonos színű csúcsok között nem vezet él.

Mi igaz az alábbiak közül, ha feltételezzük, hogy ?

Az algoritmusról azt tudjuk, hogy lépésszáma a bemenet hosszának, -nek a függvényében , a algoritmusról pedig azt tudjuk, hogy lépésszáma a bemenet hosszának, -nek a függvényében .

Melyik igaz az alábbiak közül?

Adott darab csúcs, melyek meg vannak címkézve az számokkal. Hány különböző olyan egyszerű gráf adható meg ezeken a csúcsokon, amelyben az 1-es csúcsnak darab szomszédja van, a 2-es csúcsnak pedig egy? 

Két gráfot akkor tekintünk különbözőnek, ha van legalább egy olyan pontpár, ami az egyikben össze van kötve, de a másikban nincsen. 

Legyen egy   csúcsú egyszerű, irányítatlan gráf (). Tekintsük a következő tulajdonságot:

A gráf csúcsai kiszínezhetők színt használva helyesen úgy, hogy minden színt pontosan kétszer használunk.

Az alábbiak közül melyik írja le pontosan az ezen tulajdonságú gráfokat?

Mennyi a fenti eljárásban az tömb kitöltésének lépésszáma?