Пусть n -- кол-во вершин в графе, A -- матрица расстояний размера [n x n], в {} будем записывать сложностью проделанных операций.
Считаем, что поисковую задачу мы умеем решать эффективно (за полиномиальное время). Для начала поймём, есть ли хоть один гамильтонов цикл для матрицы A:
"Найдём максимальный элемент в матрице A, обозначим его m" -- {O(n^2)}
"Существует ли цикл веса не более n * m, проходящий по всем вершинам графа?" -- {полиномиальное время по условию}
Если не существует, то задача решена, если существует, то:
"Организуем бинарный поиск на отрезке [n; n * m]" -- {log(n(m - 1))} (если m экспоненциально зависит от n, то поиск эффективен, если же двойная экспонента, то уже нет. problem!!).
Всего в графе не более n * (n - 1) рёбер, т.е. O(n^2). Для нахождения гамильтонова цикла будем выбрасывать по одному рандомному ребру и проверять, остался ли гамильтонов цикл в графе. Как только проверка показывает, что цикла нет, мы возвращаем только что удалённое ребро и помечаем его, как принадлежащее гамильтонову циклу. Отмеченные рёбра повторно не удаляются. Таким образом за O(n^2) операций удаления и O(n^2) эффективных операций проверки мы найдём сам цикл.
SAT является частным случае задачи stingy SAT при k = n, где n -- число переменных в формуле. SAT является NPC (NP complete), а задача не может быть проще, чем частный случай, значит stingy SAT тоже является NPC.
а -- решение проверяется за полиномиальное время б -- здесь сведение только в одну сторону. Не любая задача о клике сводится к задаче о 3клике таким образом в -- Ясно, что множество вершин C ⊆ V является вершинным покрытием в G тогда и только тогда, когда его дополнение V − C является кликой в G г --