APX

계산 복잡성 이론에서 클래스 APX("대략 가능"의 약어)는 상수(또는 단수에 대한 상수 인자 근사 알고리즘)로 경계된 근사비를 가진 다항식 시간 근사 알고리즘을 허용하는 NP 최적화 문제의 집합이다.간단히 말해서, 이 세분류의 문제들은 최적의 답의 어떤 고정된 승법 요소 안에서 답을 찾을 수 있는 효율적인 알고리즘을 가지고 있다.

알고리즘이 발견한 솔루션이 최적 솔루션보다 최대 $f{\displaystyle (n)}$ ${\displaystyle$n}배$$ 낮은 f(n)의 곱셈 계수 ${\displaystyle$ n$}$에 대한 근사 알고리즘을 f($n{\displaystyle }$$$) {\displaystyle $f(n)}$ 입력 크기 $n$에 대한 f(n$$) ${\displaystystystything$ 알고리즘이라고 한다.여기서 $f{\displaystyle }$(${\displaystyle n}$) ${\displaystyle f(n)}$을(를) 근사비라고 한다$$.APX의 문제는 근사 비율 f${\displaystyle }$(${\displaystyle n}$ )${\displaystyle f(n)}$이(가) 상수 $c{\displaystyle }$ ${\displaystyle c}$인 알고리즘을 사용하는 것이다$.$근사 비율은 일반적으로 1보다 큰 것으로 알려져 있다.최소화 문제의 $경우{\displaystyle }$f (${\displaystyle n}$)$${\$디스플레이 스타일$ f$(n)}$이(가) 발견된 솔루션의 점수를 최적 솔루션의 점수로 나눈$$ 반면, 최대화 문제의 경우 그 반대다.열등한 솔루션이 더 작은 점수를 갖는 최대화 문제의 경우, $f{\displaystyle }$(${\displaystyle n}$) ${\displaystyle$ f$(n)}$은(는) 1보다 작은 것으로 명시되기도$$ 한다. 이 경우, $f{\displaystyle }$(${\displaystyle n)}$ ${\displaystyle f(n)}$의 역수는 발견된 솔루션의 점수 대 최적 솔루션의 점수 비율이다$$.

최적 1보다 나쁜 모든 승수 인자에 대해 그 인자 내에서 문제를 해결하는 다항 시간 알고리즘이 있다면 문제는 다항 시간 근사 체계(PTAS)를 갖는다고 한다.P = NP가 아닌 한 APX에는 있지만 PTAS는 없는 문제가 있으므로 PTAS와 관련된 문제의 등급은 APX에 엄격히 포함되어 있다.그러한 문제 중 하나는 쓰레기통 포장 문제다.

APX-강성 및 APX-완전성

문제는 APX의 모든 문제에서 그 문제로 PTAS가 감소하는 경우 APX-hard이며, APX-hard 및 APX에서도 문제가 발생하는 경우 APX-완전하다고 한다.P ≠ NP ⇒ PTAS ≠ APX의 결과로 P ≠ NP를 가정할 경우, APX-하드 문제는 PTAS를 가지고 있지 않다.실제로 APX-완전성을 입증하기 위해 한 문제를 다른 문제로 축소하는 것은 종종 L-축소 같은 다른 감소 방법을 사용하여 수행되는데, 이는 PTAS 감소를 의미한다.

예

가장 간단한 APX 완성 문제 중 하나는 MAX-3SAT-3로, 부울 만족도 문제의 변형이다.이 문제에서 우리는 각 변수가 최대 3번 나타나는 결합 정상 형태의 부울 공식을 가지고 있으며, 변수에 참/거짓 값을 한 번 할당함으로써 동시에 충족될 수 있는 절의 최대 수를 알고자 한다.

기타 APX 완료 문제는 다음과 같다.

• 최대 독립도 그래프 설정(여기서 근사 비율은 그래프의 최대 정도에 따라 다르지만 최대도가 고정되어 있으면 일정함).
• 최소 꼭지점 커버.최대 독립형 세트의 보어는 꼭지점 커버여야 한다.
• 최소 지배력은 경계도 그래프로 설정된다.
• 그래프의 거리가 메트릭 조건을 충족할 경우 여행 중인 세일즈맨 문제.TSP는 일반적인 경우 NPO 완료.
• 세트 커버에서 L 축소를 통한 토큰 재구성 문제.

관련 복잡도 클래스

PTAS

PTAS(다항식 시간 근사 체계)는 입력 크기에 대한 다항식 시간인 1을 제외하고 어떤 상수 요인 내에서 근사하게 추정할 수 있는 문제로 구성되지만 다항식은 그러한 요인에 따라 달라진다.이 클래스는 APX의 하위 집합이다.

APX중간

P = NP가 아닌 한, APX에는 PTAS나 APX-완전하지 않은 문제가 존재한다.그러한 문제는 PTAS 문제와 APX 완료 문제 사이에 경도가 있다고 생각할 수 있으며, APX-중간이라고 할 수도 있다.쓰레기통 포장 문제는 APX중간으로 생각된다.알려진 PTAS가 없음에도 불구하고 빈패킹 문제에는 최적의 솔루션이 클 때 PTAS처럼 작용하는 몇 가지 "아셉토틱 PTAS" 알고리즘이 있어 직관적으로 APX-하드 문제보다 쉬울 수 있다.

잠재적으로 APX 중간 문제의 또 다른 예로는 최소 에지 색소가 있다.

f(n)-APX

또한 복잡도 클래스 $f{\displaystyle }$(${\displaystyle n}$) ${\displaystyle f(n)}$ -APX의$$ 패밀리를 정의할 수 있으며, 여기서 $f{\displaystyle }$(${\displaystyle n}$${\displaystyle )}$ ${\displaystyle f(n)}$ -APX는$$ $O{\displaystyle }$(${\displaystyle f}$)${\displaystyle$ O$(f(n)}$ 근사$$ 비율을 갖는 다항 시간 근사 알고리즘에 대한 문제를 포함한다.$f{\displaystyle }$( ${\displaystyle n}$) ${\displaystyle f(n)}$ -APX 완료$$ 클래스를 유사하게 정의할 수 있다. 이러한 클래스에는 잘 알려진 최적화 문제가 포함되어 있다.Log-APX-완전성과 폴리-APX-완전성은 PTAS-축소보다는 AP-축소 관점에서 정의된다. 이는 PTAS축소가 APX에 충분하더라도 Log-APX와 Poly-APX의 멤버십을 보존할 만큼 강력하지 않기 때문이다.

입력 크기의 인자 로그 내에서 효율적으로 추정할 수 있는 가장 어려운 문제들로 구성된 로그-APX-완전성은 정도가 제한되지 않을 때 최소 지배 집합을 포함한다.

입력 크기에서 요인 다항식 내에서 효율적으로 근사할 수 있는 가장 어려운 문제로 구성된 폴리-APX 완전성은 일반 사례에서 최대 독립 세트를 포함한다.

또한 exp-APX-완전한 문제들이 존재하는데, 여기서 근사비는 입력크기에서 지수적이다.이것은 근사치가 문제 인스턴스 내의 숫자 값에 따라 달라질 수 있다. 이러한 숫자는 그 값에서 공간 로그로 표현될 수 있으며, 따라서 지수 인자가 될 수 있다.

참고 항목

• 근사 보존 감소
• 복잡도 등급
• 근사 알고리즘
• 최대/최소 CSP/Ones 분류 이론 - 부울 관계에 대한 문제를 근사치 복잡성 등급으로 기계적으로 분류할 수 있는 이론 집합
• MaxSNP - 밀접하게 연관된 하위 클래스

참조

• 복잡성 동물원: APX
• C. 파파디미트리오와 M.얀나카키스.최적화, 근사치 및 복잡성 클래스.컴퓨터 및 시스템 과학 저널, 43:425–440, 1991.
• 피에루이지 크레스켄지, 비고 칸, 마그누스 할도르손, 마렉 카르핀스키, 게르하르트 우잉거.최대 만족도 2007-04-13을 웨이백 머신에 보관.NP 최적화 문제의 개요 2007-04-05 Wayback Machine에 보관.