Алгоритми та структури даних · Senior · Запитання 57 з 75
Що означає, що задача NP-повна?
- 1Доведено, що жоден алгоритм ніколи не зможе її розв'язати
- ✓Правильна відповідь: Вона в NP, і до неї поліноміально зводиться будь-яка задача з NP
- 3Її може розв'язати лише недетермінований комп'ютер
Пояснення
Розв'язки можна швидко перевірити, але поліноміального алгоритму, щоб їх знайти, не відомо. Поліноміальний алгоритм для будь-якої NP-повної задачі розв'язав би весь NP. Приклади: SAT, розфарбування графа, subset sum.