잘 알려진 바와 같이, NP-hard 최적화 문제는 PTAS를 갖는 것에서부터 임의의 요소 내에서 추정 할 수없는 것까지 모든 범위의 다양한 근사 비율을 가질 수있다. 그 사이에는 다양한 상수 , p o l y ( n ) 등이 있습니다.
O(logn)poly(n)
가능한 비율 세트에 대해 알려진 것은 무엇입니까? 어떤 종류의 “근사 계층”을 증명할 수 있습니까? 공식적으로, 어떤 함수 과 g ( n )에 대해 근사 비율 f ( n ) ≤ α < g ( n )에 문제가 있음을 증명할 수 있습니까?
f(n)g(n)
f(n)≤α<g(n)
의 경우 근사 비가 정확히 α에 문제가 있습니까?
α=O(1)α
답변
⊆
⊆
⊆
다음과 같은 결과에서 가능한 비율 세트에 대한 많은 결과가 있습니다.
P||Cmax∈
∖
P=NP
APX / NPO-PB-hard 문제를 정의합니다.
일부 참고 문헌 :
- PTAS : M. Cesati 및 L. Trevisan. 다항식 시간 근사 방식의 효율성, 1997.
- NPOPB에서 : V. Kann. 일부 NPO PB 완전 최대화 문제의 근사성에 대한 강력한 하한
그러나 나는 최선을 확인하는 것입니다 제안 복잡성 동물원 은, 심지어 예에 대한 더 많은 정보와 참조를 가지고 있기 때문에 위키 백과
α=O(1)
답변
나는 여전히 질문 아래 수레 쉬의 의견이 어떤 비율도 가능하다는 것을 보여주기에 충분하다고 생각한다. 이를 확신하지 못하면 예를 들어 부울 제약 조건 만족도 (CSP)를 볼 수 있습니다.
P:{0,1}k→{0,1}
k
n≫k
x1,…,xn
m
P(λ1,…,λk)
λi
3SAT
P(x1,x2,x3)=x1∨x2∨x3
ρ(P)
2k
P
3SAT
7/8
ρ(P)
P
ρ(P)
ρ(P)+ϵ
ϵ>0
ρ(P)
P
ρ(P)
P
Austrin과 Johan Håstad, 임의로 지원되는 독립성과 저항, SIAM Journal on Computing, vol. 40 번 1, pp. 1-27, 2011.
α
α′≤α
ρ(P)=α′