Tekintsük azt az eldöntési feladatot, ahol egy irányított <math>G</math> gráfról azt szeretnénk eldönteni, hogy van-e két olyan <math>s</math> és <math>t</math> csúcsa, hogy <math>s</math> -ből van irányított út <math>t</math> -be, de <math>t</math> -ből nincsen irányított út <math>s</math> -be (2022 jan)Melyik állítás igaz az alábbiak közül, ha feltesszük, hogy <math>P \neq NP</math> ?
A probléma <math>P</math> -ben és <math>NP</math> -ben is benne van. 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>NP</math> -teljes.