NP-полные задачи и сводимость задач, Теория сложности вычислений

1. Предположим, что у нас есть (чёрный ящик) функция sat(φ), которая если ей дать булеву формулу φ - phi, решает удовлетворима φ или нет (выводит булево значение).
Спроектируйте алгоритм, который для φ в КНФ составляет удовлетворяющее присваивание, если оно существует. Алгоритм должен работать за полиномиальное время если мы полагаем, что вызов sat() происходит за константное время. Более того, алгоритм должен работать за полиномиальное время если мы полагаем, что вызов sat() происходит за полиномиальное время
2. Покажите, что задача SET-SPLITTING (РАЗДЕЛЕНИЕ-МНОЖЕСТВА) является NP-полной. Используйте задачу 3-SAT (3-ВЫП)
3. Покажите, что задача HALF-CLIQUE (ПОЛУ-КЛИКА) является NP-полной. Используйте одну из следующих задач: SAT (ВЫП), 3-SAT (3-ВЫП), VERTEX-COVER (ВЕРШИННОЕ-ПОКРЫТИЕ), CLIQUE (КЛИКА), 3D-MATCHING (3Д-СООТВЕТСТВИЕ), HAMILTONIAN-CYCLE (ГАМИЛЬТОНОВ-ЦИКЛ), TEAVELLING-SALESPERSON (ЗАДАЧА-КОММИВОЯЖЁРА), PARTITION-PROBLEM (ЗАДАЧА-РАЗБИЕНИЯ-МНОЖЕСТВА-ЧИСЕЛ).