solutions

###8.1

Пусть n -- кол-во вершин в графе, A -- матрица расстояний размера [n x n].

Будем следить за сложностью проделанных операций.

Считаем, что поисковую задачу мы умеем решать эффективно (за полиномиальное время). Для начала поймём, есть ли хоть один гамильтонов цикл для матрицы A:

"Найдём максимальный элемент в матрице A, обозначим его m" (O(n^2))

"Существует ли цикл веса не более n * m, проходящий по всем вершинам графа?" (полиномиальное время по условию)

Если не существует, то задача решена.

Если существует, то:

"Организуем бинарный поиск на отрезке [n; n * m]" (log(n(m - 1)) -- если m экспоненциально зависит от n, то поиск эффективен, если же двойная экспонента, то уже нет. problem!!).

8.2

Всего в графе не более n * (n - 1) рёбер, т.е. O(n^2). Для нахождения гамильтонова цикла будем выбрасывать по одному рандомному ребру и проверять, остался ли гамильтонов цикл в графе. Как только проверка показывает, что цикла нет, мы возвращаем только что удалённое ребро и помечаем его, как принадлежащее гамильтонову циклу. Отмеченные рёбра повторно не удаляются. Таким образом за O(n^2) операций удаления и O(n^2) эффективных операций проверки мы найдём сам цикл.

8.3

Построим сведение stingy SAT к SAT. Пусть n -- кол-во переменных в задаче stingy SAT, k = n, тогда найдём выполняющий набор, в котором не более k переменным присвоено значение true. А это и есть формулировка задачи SAT, которая является NPC (NP complete).

8.4