다항 시간 근사 해법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 종류
- 2.1. 결정적 (Deterministic) PTAS
- 2.2. 확률적 (Randomized) PTAS
3. 복잡도 클래스
4. 한계
참조

1. 개요

다항 시간 근사 해법(PTAS)은 주어진 입력에 대해 최적해에 근접하는 해를 다항 시간 내에 찾는 알고리즘을 의미한다. 결정적 PTAS, 효율적인 다항 시간 근사 기법(EPTAS), 완전 다항 시간 근사 기법(FPTAS), 준 다항 시간 근사 기법(QPTAS) 등이 존재하며, 확률적 PTAS에는 PRAS, EPRAS, FPRAS 등이 있다. PTAS는 APX의 부분 집합이며, P=NP가 아니라면 FPTAS ⊊ PTAS ⊊ APX 관계가 성립한다. PTAS는 최적화 문제의 복잡도 클래스로도 사용되며, PTAS 환원, L-환원, P-환원 등을 통해 문제의 PTAS 여부를 판별한다.

더 읽어볼만한 페이지

근사 알고리즘 - 최근접 이웃 탐색
최근접 이웃 탐색은 다차원 공간에서 주어진 질의와 가장 유사한 데이터를 찾는 최적화 문제로, 데이터 압축, 데이터 마이닝, 기계 학습 등 다양한 분야에서 활용되며, 효율적인 탐색을 위해 다양한 알고리즘이 개발되고 있고, 개인 정보 보호 및 데이터 편향성과 같은 윤리적 문제에 대한 고려도 중요해지고 있다.
근사 알고리즘 - 크리스토피데스 알고리즘
크리스토피데스 알고리즘은 삼각 부등식을 만족하는 완전 그래프에서 외판원 문제의 근사해를 구하는 O(n³) 복잡도의 알고리즘으로, 최소 비용 신장 트리 생성, 홀수 차수 정점 집합 식별, 최소 가중치 완전 매칭 계산을 통해 해밀턴 회로를 구성하며 최적해의 3/2 이내의 근사 비율을 보장하고 다양한 분야에 응용된다.

다항 시간 근사 해법
개요
종류	근사 알고리즘
문제 유형	최적화 문제
특징	주어진 오차 범위 내에서 최적해에 가까운 해를 다항 시간 내에 찾는 것을 보장
오차 범위 (ε)	ε > 0
근사 비율	1 + ε 또는 1 – ε
해의 품질	(1 + ε)L (L은 최적해의 비용)
복잡도
실행 시간 (일반적인 경우)	O(n)
실행 시간 (지수 함수)	O(n)
영어 명칭
영어	Polynomial-time approximation scheme

2. 종류

다항 시간 근사 해법(PTAS)은 실행 시간과 근사 비율 $\varepsilon$ 의 관계, 그리고 알고리즘의 결정성 여부에 따라 여러 종류로 나뉜다.

주요 결정론적 PTAS 종류는 다음과 같다.

'''효율적인 다항 시간 근사 기법''' ('''EPTAS'''^[5]): 실행 시간이 문제 크기 $n$ 에 대해 $O(n^c)$ 형태이다 ( $c$ 는 $\varepsilon$ 와 무관한 상수).
'''완전 다항 시간 근사 기법''' ('''FPTAS'''^[6]): 실행 시간이 문제 크기 $n$ 과 $1/\varepsilon$ 모두에 대해 다항 시간이다. 배낭 문제가 대표적인 예시다.^[12]
'''준 다항 시간 근사 기법''' ('''QPTAS'''^[8]): 실행 시간이 $n^{polylog(n)}$ 형태인 준 다항 시간이다.

P≠NP라는 가정 하에서,

FPTAS \subsetneq PTAS \subsetneq APX

관계가 성립하며, 이는 APX-어려운 문제는 PTAS를 가질 수 없음을 시사한다.

확률적 알고리즘을 사용하는 PTAS도 있다.

'''다항 시간 난수 근사 기법''' ('''PRAS'''^[9]): 다항 시간 내에 '높은 확률'로 $1+\varepsilon$ 근사해를 찾는 알고리즘이다. 실행 시간 제약에 따라 '''효율적 다항 시간 난수 근사 기법'''('''EPRAS'''^[10])과 '''완전 다항 시간 난수 근사 기법'''('''FPRAS'''^[11])으로 더 세분화된다.^[12]

2. 1. 결정적 (Deterministic) PTAS

PTAS 알고리즘은 근사 비율

\varepsilon

이 작아질수록 실행 시간의 다항식 지수가

O(n^{(1/\varepsilon)!})

처럼 급격하게 증가할 수 있다는 실용적인 문제점을 가진다. 이러한 문제를 해결하기 위해 여러 종류의 결정적 PTAS가 정의되었다.

'''효율적인 다항 시간 근사 기법''' ('''EPTAS'''^[5], Efficient PTAS): 실행 시간이 $\varepsilon$ 과 독립적인 상수 $c$ 에 대해 $O(n^c)$ 인 PTAS를 의미한다. 이는 문제 크기 $n$ 의 증가가 실행 시간에 미치는 상대적 영향이 사용되는 $\varepsilon$ 값에 관계없이 일정하다는 장점을 가진다. 하지만 빅 오 표기법 내의 상수는 여전히 $\varepsilon$ 값에 따라 임의로 커질 수 있다. EPTAS는 매개변수가 $\varepsilon$ 인 FPT 시간 내에 실행된다.

'''완전 다항 시간 근사 기법''' ('''FPTAS'''^[6], Fully PTAS): 실행 시간이 문제 크기 $n$ 과 $1/\varepsilon$ 모두에 대해 다항 시간인 PTAS이다. 이는 가장 이상적인 형태의 PTAS로 여겨진다. 배낭 문제는 FPTAS를 가지는 대표적인 문제이다.^[12] 하지만 P≠NP라는 가정 하에서, 다항식적으로 유계인 목적 함수를 갖는 어떤 강력한 NP-완전 최적화 문제도 FPTAS를 가질 수 없다.^[12] 그러나 그 역이 항상 성립하는 것은 아니다. 예를 들어, 두 개의 제약 조건을 가진 배낭 문제는 FPTAS를 가지지 않지만, 목적 함수가 다항식적으로 유계인 경우에도 강력한 NP-완전 문제는 아니다.^[7]

'''준 다항 시간 근사 기법''' ('''QPTAS'''^[8], Quasi-PTAS): 각 고정된 $\varepsilon > 0$ 에 대해 시간 복잡도가 $n^{polylog(n)}$ 인 PTAS이다. 여기서 $polylog(n)$ 은 $n$ 에 대한 폴리로그 함수를 의미한다.

P≠NP라는 가정 하에서, 이들 근사 기법 클래스 사이에는 다음과 같은 포함 관계가 성립한다:

FPTAS \subsetneq PTAS \subsetneq APX

.^[2] 이는 APX-hard 문제는 PTAS를 가질 수 없음을 의미한다.

또한, PTAS는 문제의 특정 매개변수화에 대해 FPT 시간 내에 실행될 수도 있으며, 이는 매개변수화 근사 기법이라는 분야로 이어진다.

2. 2. 확률적 (Randomized) PTAS

어떤 문제들은 다항 시간 근사 해법을 갖지 않지만, 유사한 속성을 가진 확률적 알고리즘을 통해 근사해를 찾을 수 있다. 이를 '''다항 시간 확률적 근사 해법'''(Polynomial-time Randomized Approximation Scheme) 또는 '''PRAS'''라고 부른다.^[9]^[3] PRAS는 최적화 문제의 인스턴스와 매개변수

\varepsilon>0

을 입력으로 받아, 다항 시간 내에 최적해의

1+\varepsilon

배 이하인 해를 '높은 확률'로 찾아내는 알고리즘이다. 여기서 '높은 확률'은 일반적으로 3/4보다 큰 확률을 의미하지만, 대부분의 확률적 복잡도 종류와 마찬가지로 정의 자체는 이 구체적인 값에 대해 강건하다(최소 요구 사항은 보통 1/2보다 크다).^[3]^[12]

PTAS와 마찬가지로 PRAS는 문제 크기

n

에 대해 다항 시간 안에 실행되어야 하지만,

\varepsilon

값에 대해서는 반드시 그럴 필요는 없다.

\varepsilon

에 대한 실행 시간 제약 조건에 따라 다음과 같이 더 세분화할 수 있다.^[3]^[12]

'''효율적 다항 시간 확률적 근사 해법''' (Efficient PRAS, '''EPRAS'''^[10]): EPTAS와 유사하게, 실행 시간이 $n$ 에 대해서는 다항 시간이고 $1/\varepsilon$ 에 대한 의존성이 특정 함수 형태(예: $1/\varepsilon$ 의 다항식 곱하기 $n$ 의 다항식)로 제한되는 PRAS이다.^[3]^[12]
'''완전 다항 시간 확률적 근사 해법''' (Fully PRAS, '''FPRAS'''^[11]): FPTAS와 유사하게, 실행 시간이 $n$ 과 $1/\varepsilon$ 모두에 대해 다항 시간인 PRAS이다.^[3]^[12]

3. 복잡도 클래스

PTAS라는 용어는 PTAS를 갖는 최적화 문제의 클래스를 지칭하는 데에도 사용될 수 있다. PTAS는 APX의 부분 집합이며, P = NP가 아니라면 진부분집합이다. 즉, P ≠ NP라면 PTAS는 APX의 진부분집합이다 (PTAS ⊊ APX).

어떤 문제가 PTAS에 속한다는 것은 PTAS 환원, L-환원, 또는 P-환원과 같은 환원을 사용하여 보일 수 있다. 이러한 환원들은 PTAS에 속하는 성질을 보존하며, 이를 통해 특정 문제가 PTAS-완전함을 입증하는 데 사용될 수도 있다.

반대로, 어떤 문제가 PTAS에 속하지 않음(즉, 해당 문제에 대한 PTAS가 존재하지 않음)을 보이는 것은 그 문제가 APX-어렵다는 것을 증명함으로써 가능하다. 만약 APX-어려운 문제에 대해 PTAS가 존재한다면, 이는 P = NP라는 결론으로 이어지기 때문이다. APX-어려움은 일반적으로 PTAS 환원 또는 AP-환원을 통해 증명된다.

4. 한계

PTAS 알고리즘이 가진 현실적인 문제점은 근사 비율 ε 값을 작게 할수록, 즉 더 좋은 근사 해를 원할수록 실행 시간의 다항식 차수가 급격하게 증가할 수 있다는 점이다. 예를 들어 실행 시간이 ''O''(n^(1/ε)!)와 같이 ε에 대해 매우 민감하게 증가하는 경우가 있다.

이러한 한계를 극복하기 위해 몇 가지 더 효율적인 근사 기법들이 정의되었다.

'''효율적인 다항 시간 근사 기법''' ('''EPTAS''', Efficient Polynomial-Time Approximation Scheme)^[5]: 실행 시간이 ''O''(n^c) 형태이며, 여기서 지수 c는 ε와 독립적인 상수이다. 즉, 문제 크기 n의 증가가 실행 시간에 미치는 상대적 영향은 ε 값에 관계없이 동일하다. 그러나 빅 오 표기법의 상수 인자는 여전히 ε에 의존하여 커질 수 있다. EPTAS는 FPT 시간 내에 실행된다고 볼 수 있다 (매개변수는 ε).
'''완전 다항 시간 근사 기법''' ('''FPTAS''', Fully Polynomial-Time Approximation Scheme)^[6]: 알고리즘의 실행 시간이 문제 크기 n과 1/ε 모두에 대해 다항 시간인, 더 강력한 조건을 만족하는 기법이다. 배낭 문제는 FPTAS가 존재하는 대표적인 문제이다.

하지만 FPTAS도 한계가 있다. P≠NP라는 가정 하에, 목적 함수 값이 다항식적으로 유계된(다항 시간적으로 제한된) 강력한 NP-완전 최적화 문제는 FPTAS를 가질 수 없다.^[12] 그러나 이 명제의 역은 성립하지 않는다. 예를 들어, 제약 조건이 2개인 배낭 문제는 FPTAS를 갖지 않지만, 강력한 NP-완전 문제는 아니다 (목적 함수가 다항식적으로 유계인 경우).^[7]

근본적으로, P≠NP라는 가정 하에서는 다음과 같은 포함 관계가 성립한다.^[2]

FPTAS ⊊ PTAS ⊊ APX

이는 곧, APX-난해(APX-hard) 문제는 PTAS를 가질 수 없음을 의미한다. 즉, 어떤 상수 비율보다 더 좋게 근사하는 다항 시간 알고리즘이 존재하지 않는 문제들이 있다는 것이다.

PTAS의 또 다른 결정론적 변형으로는 '''준 다항 시간 근사 기법''' ('''QPTAS''', Quasi-Polynomial-Time Approximation Scheme)^[8]가 있다. QPTAS는 고정된 모든 ε > 0에 대해 n^polylog(n)의 시간 복잡도를 갖는다.

결정론적 PTAS를 갖지 않는 일부 문제들은 유사한 속성을 가진 확률적 알고리즘을 허용할 수 있다. 이를 '''다항 시간 확률적 근사 해법''' ('''PRAS''', Polynomial-Time Randomized Approximation Scheme)^[9]라고 한다. PRAS는 최적화 문제의 인스턴스와 매개변수 ε > 0을 입력으로 받아, 다항 시간 내에 최적해 값의 (1 + ε) 배 이하인 해를 생성할 확률이 높은 알고리즘이다. 여기서 '높은 확률'은 관습적으로 3/4 이상을 의미하지만, 대부분의 확률적 계산 복잡도 클래스는 이 구체적인 값에 대해 강건하다(최소 요구 사항은 일반적으로 1/2보다 크다). PTAS와 마찬가지로 PRAS는 n에 대해 다항 시간이어야 하지만, 1/ε에 대해서는 그럴 필요가 없다. ε에 대한 실행 시간 제약 조건에 따라 EPTAS와 유사한 '''효율적인 다항 시간 확률적 근사 해법''' ('''EPRAS''')^[10]와 FPTAS와 유사한 '''완전 다항 시간 확률적 근사 해법''' ('''FPRAS''')^[11]를 정의할 수 있다.^[3]^[12]

참조

_[1] 논문 Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems
_[2] 간행물 Lectures on Proof Verification and Approximation Algorithms https://books.google[...] Springer
_[3] 서적 Approximation Algorithms Springer
_[4] 논문 Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems
_[5] 문서 efficient polynomial-time approximation scheme
_[6] 문서 fully polynomial-time approximation scheme
_[7] 서적 Knapsack Problems Springer
_[8] 문서 quasi-polynomial-time approximation scheme
_[9] 문서 polynomial-time randomized approximation scheme
_[10] 문서 efficient polynomial-time randomized approximation scheme
_[11] 문서 fully polynomial-time randomized approximation scheme
_[12] 서적 Approximation Algorithms Springer

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com