„Záróvizsga kvíz - Algoritmusok” változatai közötti eltérés
a typo |
a typo |
||
| 96. sor: | 96. sor: | ||
== Legyen <math>X</math> az az eldöntési probléma, ahol egy irányítatlan <math>G</math> páros gráfról és egy <math>k</math> számról azt szeretnénk eldönteni, hogy van-e <math>G</math>-ben <math>k</math> élű párosítás és legyen <math>Y</math> az a kérdés, ahol egy irányítatlan <math>G</math> gráfról és egy számról azt szeretnénk eldönteni, hogy van-e <math>G</math>-ben <math>k</math> pontból álló klikk (azaz teljes gráf). (2022 jan) == | == Legyen <math>X</math> az az eldöntési probléma, ahol egy irányítatlan <math>G</math> páros gráfról és egy <math>k</math> számról azt szeretnénk eldönteni, hogy van-e <math>G</math>-ben <math>k</math> élű párosítás és legyen <math>Y</math> az a kérdés, ahol egy irányítatlan <math>G</math> gráfról és egy számról azt szeretnénk eldönteni, hogy van-e <math>G</math>-ben <math>k</math> pontból álló klikk (azaz teljes gráf). (2022 jan) == | ||
Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq NP</math>? | |||
{{Kvízkérdés|típus=egy|válasz=1}} | {{Kvízkérdés|típus=egy|válasz=1}} | ||
# <math>X</math> Karp-redukálható <math>Y</math>-ra, de <math>Y</math> nem Karp-redukálható <math>X</math>-re. | # <math>X</math> Karp-redukálható <math>Y</math>-ra, de <math>Y</math> nem Karp-redukálható <math>X</math>-re. | ||
# <math>X</math> nem Karp-redukálható <math>Y</math>-ra, de <math>Y</math> Karp-redukálható <math>X</math>-re. | # <math>X</math> nem Karp-redukálható <math>Y</math>-ra, de <math>Y</math> Karp-redukálható <math>X</math>-re. | ||