Tegyük fel, hogy NP ≠ P. Jelölje P 1

Question

Tegyük fel, hogy NP ≠ P. Jelölje  P 1  <  P 2  azt, hogy a  P 1  probléma Karp-redukálható a  P 2  problémára. Tegyük fel, hogy az  X ,  Y ,  Z  problémákra teljesül, hogy  X  <  Y ,  X  <  Z  és  Y  NP-teljes. Melyik következik ezekből?

Answer

X  NP-ben van és  Z  NP-teljes

Answer

Egyik sem helyes.

Answer

X  és  Z  is NP-teljes

Answer

X  NP-teljes, de  Z  nem feltétlenül NP-teljes

Answer

X  NP-ben van, de nem feltétlenül NP-teljes

Crowdly

Tegyük fel, hogy NP ≠ P. Jelölje P 1 < P 2 azt, hogy a P 1 probléma Karp-r...

Want instant access to all verified answers on edu.vik.bme.hu?