Tekintsük azt az eldöntési feladatot, ahol egy irányítatlan <math>G</math> gráfról azt szeretnénk eldönteni, hogy hozzá lehet-e adni legfeljebb 5 élet <math>G</math>-hez úgy, hogy a keletkező gráfban legyen 100 pontú teljes részgráf. (Új csúcsot nem adunk hozzá a gráfhoz, csak éleket húzunk be a már meglevő csúcsok közé.) (2023 jan)Melyik állítás igaz az alábbiak közül, ha feltesszük, hogy <math>P \neq N P</math> ?
A probléma <math>P</math>-ben van, de nincs <math>NP</math>-ben. A probléma <math>NP</math>-teljes és nincs <math>P</math>-ben. A probléma <math>P</math>-ben van és <math>N P</math>-teljes. A probléma <math>P</math>-ben és <math>N P</math>-ben is benne van.