근사 비율에 대한 계층 정리? 것까지 모든 범위의 다양한 근사

잘 알려진 바와 같이, NP-hard 최적화 문제는 PTAS를 갖는 것에서부터 임의의 요소 내에서 추정 할 수없는 것까지 모든 범위의 다양한 근사 비율을 가질 수있다. 그 사이에는 다양한 상수 , 등이 있습니다. $O (\log n)$

O(log⁡n)

$p o l y (n)$

poly(n)

가능한 비율 세트에 대해 알려진 것은 무엇입니까? 어떤 종류의 “근사 계층”을 증명할 수 있습니까? 공식적으로, 어떤 함수 과 대해 근사 비율 문제가 있음을 증명할 수 있습니까? $f (n)$

f(n)

$g (n)$

g(n)

$f (n) \leq α < g (n)$

f(n)≤α<g(n)

의 경우 근사 비가 정확히 문제가 있습니까? $α = O (1)$

α=O(1)

$α$

답변

$\subseteq$

⊆

$\subseteq$

⊆

$\subseteq$

⊆

다음과 같은 결과에서 가능한 비율 세트에 대한 많은 결과가 있습니다.

$P | | C_{m a x} \in$
P||Cmax∈
$∖$
∖
$P = N P$
P=NP

APX / NPO-PB-hard 문제를 정의합니다.

일부 참고 문헌 :

PTAS : M. Cesati 및 L. Trevisan. 다항식 시간 근사 방식의 효율성, 1997.
NPOPB에서 : V. Kann. 일부 NPO PB 완전 최대화 문제의 근사성에 대한 강력한 하한

그러나 나는 최선을 확인하는 것입니다 제안 복잡성 동물원 은, 심지어 예에 대한 더 많은 정보와 참조를 가지고 있기 때문에 위키 백과

$α = O (1)$

α=O(1)

답변

나는 여전히 질문 아래 수레 쉬의 의견이 어떤 비율도 가능하다는 것을 보여주기에 충분하다고 생각한다. 이를 확신하지 못하면 예를 들어 부울 제약 조건 만족도 (CSP)를 볼 수 있습니다.

$P : {0, 1}^{k} \to {0, 1}$

P:{0,1}k→{0,1}

$k$

$n ≫ k$

n≫k

$x_{1}, \dots, x_{n}$

x1,…,xn

$m$

$P (λ_{1}, \dots, λ_{k})$

P(λ1,…,λk)

$λ_{i}$

λi

$3 S A T$

3SAT

$P (x_{1}, x_{2}, x_{3}) = x_{1} \lor x_{2} \lor x_{3}$

P(x1,x2,x3)=x1∨x2∨x3

$ρ (P)$

ρ(P)

$2^{k}$

$P$

$3 S A T$

3SAT

$7 / 8$

7/8

$ρ (P)$

ρ(P)

$P$

$ρ (P)$

ρ(P)

$ρ (P) + ϵ$

ρ(P)+ϵ

$ϵ > 0$

ϵ>0

$ρ (P)$

ρ(P)

$P$

$ρ (P)$

ρ(P)

$P$

Austrin과 Johan Håstad, 임의로 지원되는 독립성과 저항, SIAM Journal on Computing, vol. 40 번 1, pp. 1-27, 2011.

$α$

$α^{'} \leq α$

α′≤α

$ρ (P) = α^{'}$

ρ(P)=α′

How IT

언제든지 물어보세요.

근사 비율에 대한 계층 정리? 것까지 모든 범위의 다양한 근사

답변

답변

답변