Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 52

Рассмотрим два языка L1 и L2 каждый на алфавите ∑. Пусть f: ∑ → ∑ — вычисляемая биекция за полиномиальное время, такая что (∀ x) [x ∈ L1 тогда и только тогда, когда f (x) ∈ L2].

Далее, пусть f -1 также будет вычисляться за полиномиальное время.

Что из следующего НЕ МОЖЕТ быть правдой?
(A) L1 ∈ P и L2 конечно
(B) L1 ∈ NP и L2 ∈ P
(C) L1 неразрешима и L2 разрешима
(D) L1 рекурсивно перечислимо, а L2 рекурсивно

Ответ: (с)
Объяснение: У нас есть однозначное отображение для всех экземпляров от L1 до L2.

Рекомендуемые посты:

ВОРОТА | GATE-CS-2003 | Вопрос 52

0.00 (0%) 0 votes