하나는 얻을 수 MAX3SAT에 대한 근사치를한다는 점에서 실행 이 O ( ε의 N ) 너무 많은 문제가없는 시간입니다. 여기 아이디어가 있습니다. 변수 세트를 각각 ε n 변수 의 O ( 1 / ε ) 그룹으로 나눕니다 . 각 그룹에 대해 모든 노력 이 ε N 그룹의 변수를 할당하는 방법을. 각각 감소 화학식 들어 Karloff Zwick의 실행 및 7 / 8 -approximation한다. 이러한 모든 시행에서 최대 수의 조항을 만족하는 과제를 출력합니다.7/8+ε/8

$7/8+\epsilon /8$

$7/8+\varepsilon/8$2O(εn)

$2^{O(\epsilon n)}$

$2^{O(\varepsilon n)}$O(1/ε)

$O(1/\epsilon )$

$O(1/\varepsilon)$εn

$\epsilon n$

$\varepsilon n$2εn

$2^{\epsilon n}$

$2^{\varepsilon n}$7/8

$7/8$

$7/8$

요점은 최적의 할당 (해당 블록으로 제한됨)이 이미 충족 된 최대 절 수의 분율을 충족하도록 일부 가변 블록이 있다는 것입니다 . 여분의 절은 정확히 맞을 것이고 Karloff와 Zwick을 사용하여 나머지 부분의 7 / 8 을 얻습니다 .ε

$\epsilon$

$\varepsilon$7/8

$7/8$

$7/8$

동일한 유형의 근사치에 대해 시간을 얻을 수 있다면 흥미로운 질문 입니다. 3SAT를 다항식 시간에서 MAX3SAT로 줄일 수있는 “선형 PCP 추측”이 있습니다.2O(ε2n)

$2^{O({\epsilon }^{2}n)}$

$2^{O(\varepsilon^2 n)}$

• 3SAT 인스턴스를 만족할 수 있으면 MAX3SAT 인스턴스를 완전히 만족시킬 수 있습니다.
• 3SAT 인스턴스 시켰음이면 MAX3SAT 인스턴스가 아닌 만족할 및7/8+ε
  $7/8+\epsilon$

  $7/8+\varepsilon$

• 감소는 공식 크기를 만큼 증가시킵니다.poly(1/ε)
  $poly(1/\epsilon )$

  $poly(1/\varepsilon)$

이 선형 PCP 추측하는 가정 – 시간 7 / 8 + ε 모두, 근사 C 및 ε , 3SAT는 것을 수반 2 ε N 모든 시간 ε . (여기서 m 은 절 수입니다.)이 증거는 Impagliazzo, Paturi 및 Zane의 Sparsification Lemma를 사용합니다.2O(εcm)

$2^{O({\epsilon }^{c}m)}$

$2^{O(\varepsilon^c m)}$7/8+ε

$7/8+\epsilon$

$7/8+\varepsilon$c

$c$

$c$ε

$\epsilon$

$\varepsilon$2εn

$2^{\epsilon n}$

$2^{\varepsilon n}$ε

$\epsilon$

$\varepsilon$m

$m$

$m$

---

답변