Шаблон:NP-повні задачі

п о р NP-повні задачі

Класифікація	Дослідження операцій:Оптимізація:Комбінаторна оптимізація

Основи	NP-повна задача · Клас складності NP · Клас складності P

Задачі	Задача заміщення сторінок · Задача здійсненності бульових формул · Задача комівояжера · Задача листоноші · Задача пакування рюкзака · Задача про кліку · Задача про точне покриття · Задача про пакування в ємності (двомірне пакування • лінійне пакування тощо) • Задача Штейнера • Задача про вершинне покриття • Задача про незалежну множину • Задача про покриття множини · ...

Теорія складності обчислень	Теорія складності обчислень • Класи складності

Логічні ігри та головоломки	Гра в п'ятнашки (гра в N²-1) (Задача пошуку найкоротшого рішення) • Задачі, рішення яких застосовуються в Тетрисі • Задача узагальненого судоку • Задача про заповнення латинського квадрата • Задачі какуро

Списки	21 NP-повна задача Карпа · Список NP-повних задач

Дослідники	Річард Карп

Див. також	Прикладна математика • Теорія алгоритмів • Динамічне програмування

Шаблон:NP-повні задачі

Навігаційне меню

Пошук