Задачі для самостійного розв’язання
1. Якщо задача A [TEX]\in [/TEX] NP і A ≤ PB, то чи можна стверджувати, що B[TEX]\in [/TEX]NP?
2. Якщо задача A [TEX]\in [/TEX] NP і B ≤ PA, то чи можна стверджувати, що B [TEX]\in [/TEX] NP?
3. Якщо A [TEX]\in [/TEX] P, то чи можна стверджувати, що A ≤ PB для будь-якої задачі B? Доведіть.
Коментарі.
Основні відомості, щодо класів складності та проблеми зведення представлені в [13], алгоритмічна нерозв’язність викладена в працях [5,9,11,24,28].
