CNF 수식에서 SAT가 NP-HARD가되기 위해 얼마나 많은 조항이 필요합니까?

Question

$ n $ 변수로 CNF 공식에 대해 SAT는 다항식 시간에 해결할 수 있습니다. 반면에 $ n $ 변수 및 $ o (n) 인 CNF 공식을 보는 것은 어렵지 않습니다 $ 절은 NP 경도에 대해 충분합니다 (예를 들어 SAT의 경우 3 색상의 자연 공식과 관련된 인스턴스와 함께 평면 그래프에 적용됨).

우리는 $ \ text {cnfsat} -f- \ text {clauses} $ , 함수 $ f $ 인스턴스는 $ n $ 변수가있는 경우에 CNF의 수식입니다. 대부분의 $ f (n) $ 절. 이를 바탕으로, 내가 알고 싶은 것은 $ g $ $ f \ $ \ text {cnfsat} -f- \ text {clauses} $ \ text {clauses} -f- \ text {clauses} -f- \ text {clauses} -f- \ text {clauses} -f- \ text {clauses} $ 은 이미 np-hard입니다. 우리는 g= 1 (constant of clses)이 작동하지 않으며 $ g= n $ (선형 수) 작동합니다.

$ g=log n $ ? $ o (\ lg \ lg n) $ 절을 갖는 수식을 통해 CNFSAT에 대한 간단한 알고리즘이 있습니까?

Answer 1

하한. $ g \ lo c \ cdot \ sqrt {\ log n} $ 다항식 - 시간 알고리즘이 있습니다. ...에 이 아이디어는 다음과 같습니다. 일부 조항이 너무 많은 변수가 너무 많으면 몇 가지 변수가 적용되지 않고이 절을 충족시키지 않고이 절을 만족시키는 변수를 선택하는 것이 사소한 여야합니다. 우리는 다음을 반복합니다 :

가장 작은 변수를 가진 절을 찾습니다. $ x_1, \ ldots, x_k $ 이 절에 참여하는 변수가되도록하십시오.

• $ K> G $ 인 경우 전체 수식이 만족스럽게 만족 스럽습니다 (우리는 하나씩 조항을 처리하고 이전에 선택하지 않은 변수를 선택하십시오).
• 그렇지 않으면 절을 제거합니다. 우리는 $ x_1, \ ldots, x_k $
를 제거합니다.

이제 우리는 제거 된 절을 만족시켜야합니다. 대부분의 $ G $ 조항이 있기 때문에 각각은 대부분의 $ g $ 새로운 변수를 소개합니다. 그것은 대부분의 $ g ^ 2= c ^ 2 \ cdot \ log n $ 변수 전체에 있습니다. 따라서 대부분의 $ n ^ {c ^ 2} $ n ^ {c ^ 2} $ 변수 조합을 사용하고, 무차별 힘을 사용할 수 있습니다.

조건부 상한. 다음과 같은 의미에서 거의 빡빡합니다. $ n $ 변수와 $ \ ge c \ CDOT n $ 조항 (일부 $ c $ , 예 : $ 3 $ - Coloring ) $ \ alpha ^ n $ ( $ \ alpha \ in (1, 2] $ )입니다. 우리가 변화 후에도 동일한 하한이 보유하고 있음을 주목하십시오. 따라서 적어도 $ \ log ^ {1+ \ epsilon} n $ 클로스, $ \ frac {\ log ^ {1+ \ epsilon} n} C $ 변수와 실행 시간에 대한 하한 우리의 문제는

입니다

$$ \ alpha ^ {\ frac {\ log ^ {1+ \ epsilon} n} c}= n ^ {\ frac {\ log ^ \ epsilon n \ cdot \ log \ alpha} {c}}, $$

슈퍼 다항식입니다.