Рама и Шьяма попросили показать, что определенная проблема NP является NP-полной. Рам показывает уменьшение полиномиального времени от задачи 3-SAT до Π, а Шиам показывает уменьшение полиномиального времени с Π до 3-SAT. Что из следующего может быть выведено из этих сокращений?
(A) NP NP-сложный, но не NP-полный
(B) in находится в NP, но не является NP-полным
(C) NP является NP-полным
(D) Π не является NP-сложным, ни в NP
Ответ: (с)
Объяснение: Поскольку полиномиальное сокращение времени от задачи 3-SAT к Π возможно, это NP сложный процесс.
Так как полиномиальное сокращение времени от Π до 3-SAT возможно, оно NP-Complete.
Тест на этот вопрос
Рекомендуемые посты:
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 52
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 65
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 64
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 53
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 54
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 55
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 56
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 57
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 58
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 59
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 60
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 61
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 62
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 63
- ВОРОТА | Sudo GATE 2020 Mock II (10 января 2019 года) | Вопрос 65
0.00 (0%) 0 votes