Запитання для самоперевірки:
- У чому суть теореми Блюма про прискорення?
- Алгоритмічні зведення за Карпом, Куком, Тюрінгом. Яка між ними різниця і що є однаковим?
- Як довести, що завдання є NP-повним?
- Що означає, що одна задача зводиться до іншої за поліноміальний час?
- Як довести, що завдання A зводиться (за поліноміальний час) до задачі B?
- Дайте означення алгоритмічної нерозв’язності.
- Що називається характеристичною функцією множини А?
- Сформулюйте теорему Райса та її наслідки.
