Рубрики

ВОРОТА | GATE-CS-2005 | Вопрос 45

GATE

Рассмотрим три задачи решения P1, P2 и P3. Известно, что P1 разрешимо, а P2 неразрешимо. Что из следующего является ИСТИННЫМ?
(A) P3 разрешимо, если P1 сводимо к P3
(B) P3 неразрешима, если P3 сводится к P2
(C) P3 неразрешима, если P2 сводится к P3
(D) P3 разрешима, если P3 сводится к дополнению P2

Ответ: (с)
Объяснение:
Предыстория: в теории вычислительной сложности проблема решения имеет только два возможных выхода: да или нет.
Проблема решения считается разрешимой, если существует эффективный метод или алгоритм, который возвращает правильный ответ «да / нет» на эту проблему.
Проблема решения называется неразрешимой, если не существует единственного алгоритма, который всегда приводит к правильному решению «да / нет».

В терминах приводимости: A ≤ p B обозначает A — это решение задачи, приводимой к B за полиномиальное время p. Это просто означает, что экземпляр A может быть преобразован в экземпляр B, и, следуя решению B, мы можем получить решение проблемы A.
Итак, здесь мы можем сделать некоторые выводы:

1. If A ≤p B and B is decidable then A is also decidable.
This is because if there exists a specific algorithm for solving B and we can 
also reduce A to B then we can have a solution of A as well. Hence A is decidable.

However the reverse is not true i.e. if A ≤p B and A is decidable 
then B is also decidable because A can have an algorithm existing for its correct 
solution but might be the case that B does not.

2. If A ≤p B and A is undecidable then B is also undecidable.
This is because if A is undecidable even when it can be reduced to B that simply 
reflects even B cannot provide an algorithm by which we can solve B and hence A. 
So decision problem B is also undecidable.

Однако обратное здесь также неверно, т. Е. Если A ≤ p B и B неразрешима, то A также неразрешима, поскольку может существовать алгоритм для A, который может обеспечить решение A.

Используя вышеизложенные выводы, мы можем сказать, что опции 1, 2 и 4 ложны, а опция 3 верна.

Option 1: P1 ≤p P3 and given P1 is decidable gives no conclusion for P3.
Option 2: P3 ≤p P2 and given P2 is undecidable gives no conclusion for P3.
Option 3: P2 ≤p P3 and given P2 is undecidable gives conclusion for P3 to be 
          undecidable.
Option 4: P3 ≤p P2’s complement and given P2 is undecidable therefore P2’s 
           complement is also undecidable gives no conclusion for P3.

Это объяснение внес Яшика Арора.

Посетите следующие статьи, чтобы узнать больше:
неразрешимость-и-сводимости
Википедия: Сокращение_ (Сложность)

Тест на этот вопрос

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

ВОРОТА | GATE-CS-2005 | Вопрос 45

0.00 (0%) 0 votes