Введение
1. Сложность в комбинаторной оптимизации 12
1.1. Некоторые сведения из теории сводимости задач 12
1.2. Многогранники задач 18
2. Конусное разбиение и аффинная сводимость 23
2.1. Конусное разбиение 23
2.2. Аффинная сводимость 26
3. Труднорешаемые задачи 31
3.1. Задача клика 31
3.2. Задача 2-выполнимость 37
3.3. Задача разрез 39
3.4. Задача трехмерное сочетание 42
3.5. Задачи рюкзак и разбиение 47
3.6. Задача коммивояжер 57
3.6.1. Задача гамильтонов контур 58
3.6.2. Задача гамильтонов цикл 64
3.6.3. Задача коммивояжера с условием "неравенство треугольника" 66
3.7. Задача длиннейший путь 67
4. Полиномиально разрешимые задачи 70
4.1. Задача о кратчайшем пути 70
4.2. Задачи о паросочетаниях 75
Заключение 81
Список литературы 85
