Сложность

  1. Алгоритм Левина
    1. Применение: NP задачи, для которых существует ответ
    2. Идея: существует оптимальный алгоритм = программа = строка = число = константа ⇒ перебёрем
    3. Реализация for T ; for A to T ; y = launch(A, 2T, x), check(x, y)

  2. Расщепление
    1. Решаем IS ⇔ VC ⇔ Clique
    2. Обычное расщепление: T(n) = T(n-1) + T(n-deg-1)
    3. ∃ v deg[v]=1 ⇒ жадность ⇒ ∀ v deg[v] ≥ 2 ⇒ T(n) = T(n-1) + T(n-3) = [1,3] = 1.4656n (в совокупности)
    4. ∀ v deg[v]=2 ⇒ жадность ⇒ ∃ v deg[v]=3 ⇒ T(n) = T(n-1) + T(n-4) = [1,4] = 1.3803n (в совокупности)
    5. ∃ v deg[v]=2 ⇒ рассмотрим его более жирного соседа (∃ по непрерывности) ⇒ T(n-1) → T(n-3) (появилась вершина степени 1) ⇒ [3,4] = 1.2207n (данный случай)
    6. ∀ v deg[v]=3, расщепимся, появится тогда появится 2 и будет [-3,-4] в каждой ветке, итого [1+3,1+4,4+3,4+4] = [4,5,7,8] = 1.2752n (данный случай)
    7. ∃ v deg[v]=4 ⇒ T(n) = T(n-1) + T(n-5) = [1,5] = 1.3247n (в совокупности)