BPP (복잡도)

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

1. 개요
2. 정의
3. 다른 복잡도 종류와 연관성
- 3.1. 관련 복잡도 클래스
4. 성질
5. 오라클 관련 성질
참조

1. 개요

BPP(Bounded-error Probabilistic Polynomial time)는 확률적 튜링 기계를 사용하여 정의되는 복잡도 종류로, 다항 시간 내에 실행되며, 특정 조건에서 2/3 이상의 확률로 1을 출력하거나 1/3 이하의 확률로 1을 출력하는 언어를 포함한다. BPP는 ZPP와 달리 무작위 동전 던지기 결과와 관계없이 다항 시간 내에 실행되어야 하며, 결정론적 튜링 기계를 통해서도 정의할 수 있다. BPP는 오류 확률을 1/3 대신 다른 상수나 변수로 대체해도 동일한 문제 집합을 정의하며, 오류가 발생하기 쉬운 알고리즘을 여러 번 실행하여 정확도를 높이는 아이디어를 기반으로 한다. BPP는 여집합 연산에 닫혀 있으며(BPP = co-BPP), NP, RP, PP 등 다른 복잡도 종류와의 관계는 아직 완전히 밝혀지지 않았다. BPP는 P/poly에 포함되며, 소수 판별 문제와 다항식 동일성 검사와 관련이 있으며, 탈랜덤화에 대한 연구가 진행되고 있다.

더 읽어볼만한 페이지

확률적 복잡도 종류 - BQP
BQP는 양자 컴퓨터를 사용하여 정의되는 계산 복잡도 클래스이며, 유계 오차를 갖는 양자 회로군으로 정의되고, P와 BPP를 포함하며 PP, PSPACE에 포함된다.
확률적 복잡도 종류 - RP (복잡도)
RP 복잡도 클래스는 확률적 튜링 기계가 언어에 속하는 입력에 대해 1을 출력할 확률이 1/2 이상이고, 속하지 않는 입력에 대해서는 항상 0을 출력하는 문제들의 집합으로, BPP, ZPP, co-RP와 관련되며 P-NP 문제와 연관성을 갖는 다항식 항등식 검사 문제의 예시를 포함한다.

BPP (복잡도)
개요
BPP 복잡도 클래스를 다른 복잡도 클래스와 비교한 벤 다이어그램
정의	BPP는 확률적 튜링 기계에 의해 다항 시간 안에 풀릴 수 있는 판단 문제의 복잡도 종류이다.
풀이 조건	모든 입력에 대해, 기계는 2/3 이상의 확률로 정답을 낸다.
BPP 의미	BPP는 어떤 문제가 효율적인 확률적 알고리즘을 가지고 있는지를 나타낸다.
클래스 이름 의미	BPP는 유계 오차 확률적 다항 시간 (Bounded-error Probabilistic Polynomial time)을 의미한다.
상세 정보
기계 종류	BPP 문제는 확률적 튜링 기계에 의해 해결된다.
시간 복잡도	다항 시간 안에 해결 가능해야 한다.
오차 확률	모든 입력에 대해 2/3보다 작거나 같은 오차율을 갖는다.
다른 표현	2/3 대신 1/2 + ε로 표현할 수 있다 (ε > 0).
형식적 정의
정의	BPP는 다음 조건을 만족하는 확률적 튜링 기계 M이 존재하는 판정 문제 A의 집합이다. M은 모든 입력에 대해 다항 시간 안에 정지한다. 입력이 A에 속하면, M은 2/3 이상의 확률로 1을 출력한다. 입력이 A에 속하지 않으면, M은 2/3 이상의 확률로 0을 출력한다.
오차 확률 조절	오차 확률 2/3는 임의의 값 0과 1/2 사이의 값으로 변경될 수 있다.
다른 표현 (수학적)	A ∈ BPP iff there exists a probabilistic Turing machine M, that Runs in polynomial time on all inputs For all x, Pr(M outputs A(x)) ≥ 2/3
다른 복잡도 종류와의 관계
포함 관계	P ⊆ BPP ⊆ PH
BPP의 보완	BPP = co-BPP
BPP와 NP	BPP와 NP의 관계는 아직 알려지지 않았다.
알려진 사실	BPP ⊆ Σ2P ∩ Π2P
BPP 문제 예시
예시	다항식 항등성 테스트 PRIMES (소수 판별)
추가 정보
BPP의 중요성	BPP는 실용적인 계산에서 효율적으로 풀릴 수 있는 문제들을 나타내는 중요한 복잡도 종류이다.

2. 정의

BPP는 확률적 튜링 기계 또는 결정론적 튜링 기계를 사용하여 정의할 수 있다. 핵심은 다항 시간 안에 실행되며, 일정 확률 이상으로 정답을 출력해야 한다는 것이다. BPP에 대한 자세한 정의는 하위 섹션에서 확인할 수 있다.^[1]

2. 1. 확률적 튜링 기계를 사용한 정의

언어 ''L''이 '''BPP'''에 속한다는 것은 다음 조건을 만족하는 확률적 튜링 기계 ''M''이 존재함을 의미한다.^[1]

''M''은 모든 입력에 대해 다항 시간 내에 실행된다.
''L''에 속하는 모든 ''x''에 대해, ''M''은 1을 출력할 확률이 2/3 이상이다.
''L''에 속하지 않는 모든 ''x''에 대해, ''M''은 1을 출력할 확률이 1/3 이하이다.

ZPP와 달리, 기계 ''M''은 무작위 동전 던지기의 결과와 관계없이 모든 입력에 대해 다항 시간 내에 실행되어야 한다.

또는, '''BPP'''는 결정론적 튜링 기계만을 사용하여 정의할 수 있다. 언어 ''L''이 '''BPP'''에 속한다는 것은 다음 조건을 만족하는 다항식 ''p''와 결정론적 튜링 기계 ''M''이 존재함을 의미한다.^[1]

''M''은 모든 입력에 대해 다항 시간 내에 실행된다.
''L''에 속하는 모든 ''x''에 대해, ''M''(''x'',''y'') = 1을 만족하는 길이 ''p''(|''x''|)의 문자열 ''y''의 비율이 2/3 이상이다.
''L''에 속하지 않는 모든 ''x''에 대해, ''M''(''x'',''y'') = 1을 만족하는 길이 ''p''(|''x''|)의 문자열 ''y''의 비율이 1/3 이하이다.

이 정의에서, 문자열 ''y''는 확률적 튜링 기계가 수행했을 무작위 동전 던지기의 출력을 나타낸다. 일부 응용 분야에서는 이 정의가 확률적 튜링 기계를 언급하지 않으므로 더 선호된다.

실제로, 1/3의 오류 확률은 허용되지 않을 수 있지만, 정의에서 1/3을 선택하는 것은 임의적이다. 1/3 대신 0과 1/2 (배타적) 사이의 임의의 수학 상수를 사용하도록 정의를 수정해도 결과 집합 '''BPP'''는 변경되지 않는다. 예를 들어, 알고리즘이 최대 1/2¹⁰⁰의 확률로 잘못될 수 있다는 제약 조건으로 클래스를 정의하면 동일한 문제 클래스가 생성된다. 오류 확률은 상수일 필요조차 없다. 오류를 1/2 - ''n''^-''c''만큼 허용하거나, 오류를 2^{-''n''^''c''}만큼 작게 요구하여 동일한 문제 클래스가 정의되며, 여기서 ''c''는 임의의 양의 상수이고 ''n''은 입력의 길이이다. 오류 확률 선택의 이러한 유연성은 오류가 발생하기 쉬운 알고리즘을 여러 번 실행하고, 실행의 다수 결과를 사용하여 더 정확한 알고리즘을 얻는다는 아이디어를 기반으로 한다. 실행의 다수가 잘못될 확률은 Chernoff bound의 결과로 지수적으로 감소한다.^[1]

2. 2. 결정론적 튜링 기계를 사용한 정의

'''BPP'''는 결정론적 튜링 기계만을 사용하여 정의할 수도 있다. 언어 ''L''이 '''BPP'''에 속한다는 것은 다음 조건을 만족하는 다항식 ''p''와 결정론적 튜링 기계 ''M''이 존재함을 의미한다.

''M''은 모든 입력에 대해 다항 시간 내에 실행된다.
''L''에 속하는 모든 ''x''에 대해, ''M''(''x'',''y'') = 1을 만족하는 길이 ''p''(|''x''|)의 문자열 ''y''의 비율이 2/3 이상이다.
''L''에 속하지 않는 모든 ''x''에 대해, ''M''(''x'',''y'') = 1을 만족하는 길이 ''p''(|''x''|)의 문자열 ''y''의 비율이 1/3 이하이다.

이 정의에서, 문자열 ''y''는 확률적 튜링 기계가 수행했을 무작위 동전 던지기의 출력을 나타낸다. 일부 응용 분야에서는 이 정의가 확률적 튜링 기계를 언급하지 않으므로 더 선호된다.^[1]

2. 3. 오류 확률의 유연성

'''BPP''' 정의에서 오류 확률 1/3은 고정된 값이 아니며, 0과 1/2 사이의 임의의 수학 상수를 사용해도 '''BPP'''는 변하지 않는다. 예를 들어, 알고리즘이 최대 1/2¹⁰⁰의 확률로 잘못될 수 있다는 제약 조건을 사용해도 같은 문제 집합이 된다.^[1]

오류 확률은 상수일 필요도 없다. 오류 확률을 1/2 − ''n''^−''c''만큼 허용하거나, 2^{−''n^c''}만큼 작게 요구해도 같은 문제 집합이 정의된다. 여기서 ''c''는 임의의 양의 상수이고, ''n''은 입력의 길이다. 이러한 유연성은 오류가 발생하기 쉬운 알고리즘을 여러 번 실행하고, 실행 결과에 대한 다수결을 통해 더 정확한 알고리즘을 얻을 수 있다는 아이디어를 기반으로 한다. 다수결 결과가 잘못될 확률은 Chernoff bound에 의해 지수적으로 감소한다.^[1]

3. 다른 복잡도 종류와 연관성

BPP는 여집합 연산에 대해 닫혀 있으며(BPP = co-BPP), RP와 co-RP는 BPP의 부분집합이고, BPP는 PP의 부분집합이다.^[2] BPP는 PH의 부분집합이기도 하다. Sipser–Lautemann 정리에 따르면 $\mathsf{BPP} \subseteq \Sigma_2 \cap \Pi_2$ 이다.

BPP와 NP 사이의 관계는 아직 명확하게 밝혀지지 않았다.^[4] 만약 NP가 BPP의 부분집합이면 NP=RP이고 PH ⊆ BPP이다. 많은 이들은 NP-완전 문제에 대한 효율적인 해가 존재할 가능성이 낮다고 추정한다.

P에 속하는 모든 문제는 BPP에도 속한다. P = BPP인지 여부는 중요한 미해결 문제이다. 오랫동안 BPP에 속하지만 P에는 속하지 않는 문제로 여겨졌던 소수 판별법 문제는 2002년 AKS 소수 판별법의 발견으로 P에 속하는 것으로 밝혀졌다.^[2]

Adleman의 정리에 따르면 BPP는 P/poly에 포함된다.^[5] BPP는 자기 자신에 비해 낮다. 즉, BPP 문제를 즉시 해결할 수 있는 BPP 기계 (신탁기계)는 이런 별도의 능력이 없는 기계보다 강력하지 않다.

BPP의 정의에서 무작위 접근을 제거하면 복잡도 종류 P를 얻게 되며, 일반적인 튜링 기계를 양자 컴퓨터로 대체하면 BQP를 얻게 된다. 몬테 카를로 알고리즘은 BPP 문제에 대한 다항식 시간 알고리즘이며, 라스베가스 알고리즘과 비교된다.

3. 1. 관련 복잡도 클래스

'''BPP'''는 여집합 연산에 대해 닫혀 있다. 즉, '''BPP'''='''co-BPP'''이다.

P, NP, co-NP, BPP, P/poly, PH, PSPACE를 포함하는 복잡도 클래스의 포함 관계

다른 확률적 복잡도 클래스(ZPP, RP, co-RP, BQP, PP)와의 관계에서 BPP. 이들은 P를 PSPACE 내에서 일반화한다. 이러한 포함 관계가 엄격한지는 알려져 있지 않다.

'''P''' ⊆ '''BPP''' ⊆ '''PH'''가 증명되었다.
'''BPP'''와 '''NP''' 사이의 관계는 알려져 있지 않다. '''BPP'''가 '''NP'''의 부분 집합인지, '''NP'''가 '''BPP'''의 부분 집합인지, 아니면 둘 다 아닌지는 알려져 있지 않다.
만약 '''NP'''가 '''BPP'''에 포함된다면, NP-완전 문제에 대한 실용적인 해법을 의미하므로, 그럴 가능성은 낮지만, '''NP''' = '''RP'''이고 '''PH''' ⊆ '''BPP'''가 된다.^[4]
'''RP'''와 '''co-RP'''는 '''BPP'''의 부분 집합이고, '''BPP'''는 '''PP'''의 부분 집합인 것으로 알려져 있다.
Adleman의 정리에 따르면, '''BPP'''의 모든 언어는 다항식 크기의 부울 회로로 판정할 수 있다. 즉, '''BPP'''는 '''P/poly'''에 포함된다.^[5]
'''BPP'''는 보문제에 대해 닫혀 있다. 즉, '''BPP''' = co-'''BPP'''이다.
'''PP'''는 BPP와 거의 같은 개념의 클래스이지만 오차 확률이 1/2 이하이다.
'''RP'''는 YES일 때의 오차 확률은 1/2 이하이며, NO일 때는 절대 틀리지 않는 클래스이다.
'''BPP'''의 정의에서 무작위 접근을 제거하면, 복잡도 종류 '''P'''를 얻게 된다.
'''BQP'''는 BPP와 비슷하지만 튜링 기계가 아닌 양자컴퓨터에 해당한다.

4. 성질

BPP는 자기 자신에 비해 낮은 복잡도 종류이다. 즉, BPP 문제를 즉시 해결할 수 있는 BPP 기계(BPP 신탁기계)는 추가적인 능력이 없는 기계와 비교했을 때 더 강력하지 않다.

BPP는 난수를 사용하는 일반적인 튜링 기계를 나타낸다. BQP는 BPP와 유사하지만, 튜링 기계가 아닌 양자컴퓨터를 기반으로 한다.

BPP는 보수에 대해 닫혀 있다. 즉, '''BPP''' = '''co-BPP'''이다.

BPP와 NP 사이의 관계는 아직 밝혀지지 않았다. BPP가 NP의 부분 집합인지, NP가 BPP의 부분 집합인지, 아니면 둘 다 아닌지 여부는 알려져 있지 않다. 만약 NP가 BPP에 포함된다면, 이는 NP-완전 문제에 대한 실용적인 해법을 의미하므로 가능성은 낮지만, '''NP''' = '''RP'''이고 PH ⊆ '''BPP'''가 된다.^[4]

RP는 BPP의 부분 집합이고, BPP는 PP의 부분 집합으로 알려져 있다. 그러나 이 두 관계가 엄격한 포함 관계인지는 알려져 있지 않다. 이는 P가 PSPACE의 엄격한 부분 집합인지조차 알 수 없기 때문이다. BPP는 다항식 계층의 두 번째 레벨에 포함되어 있으며, 따라서 PH에 포함된다. 더 정확하게는, Sipser–Lautemann 정리에 따라 $\mathsf{BPP} \subseteq \Sigma_2 \cap \Pi_2$ 이다. 결과적으로, '''P''' = '''NP'''라면 PH가 P로 축소되므로 '''P''' = '''BPP'''가 된다. 따라서 '''P''' = '''BPP'''이거나 '''P''' ≠ '''NP'''이거나 둘 중 하나이다.

Adleman의 정리에 따르면, BPP에 속하는 모든 언어의 멤버십은 다항식 크기의 부울 회로 군에 의해 결정될 수 있다. 이는 BPP가 P/poly에 포함됨을 의미한다.^[5]

BPP는 여집합, 합집합, 교집합에 대해 닫혀있다.

4. 1. 소수 판별 문제

마닌드라 아그라왈과 그의 학생 니라즈 카얄, 니틴 삭세나는 2002년에 결정론적 알고리즘을 개발하여, 오랫동안 '''BPP'''에는 속하지만 '''P'''에는 속하지 않는 것으로 여겨졌던 소수 판별 문제가 '''P'''에 속한다는 것을 밝혔다.^[2] 이는 '''BPP'''에 속하는 문제 중 '''P'''에 속하는지 여부가 불분명한 문제의 수가 줄어들고 있음을 보여준다.

4. 2. 다항식 동일성 검사

'''BPP'''에 속하는 (사실 co-RP에 속하는) 중요한 문제의 예시로, 아직 '''P'''에 속하는지 알려지지 않은 문제는 다항식 동일성 검사이다. 이 문제는 다항식의 계수가 아니라 임의의 입력에 대한 다항식의 값에 접근할 수 있을 때, 해당 다항식이 항등적으로 0 다항식과 같은지 판별하는 문제이다. 즉, 0이 아닌 다항식을 이 값으로 평가했을 때 결과가 0이 아닌 변수 값 할당이 존재하는가를 묻는 것이다. 여기서 ''d''는 다항식의 총 차수이며, 오류 확률을 제한하기 위해 각 변수의 값을 최소 ''d'' 값의 유한 부분 집합에서 균일하게 무작위로 선택하는 것으로 충분하다.^[2]

4. 3. 탈랜덤화(Derandomization)

대부분의 전문가들은 특정 조건을 만족하는 강력한 의사 난수 생성기가 존재한다고 추측한다. 이러한 생성기는 모든 다항 시간 확률적 알고리즘에서 실제 난수를 대체하여 구별할 수 없는 결과를 생성할 수 있다. 이 추측은 무작위성이 다항 시간 계산에 추가적인 계산 능력을 제공하지 않는다는 것을 의미하며, 즉 '''P''' = '''RP''' = '''BPP'''임을 뜻한다. 더 나아가, '''P''' = '''BPP'''라는 가정은 어떤 의미에서 강력한 의사 난수 생성기의 존재와 동등하다고 볼 수 있다.

러슬로 바바이, 랜스 포트노우, 노암 니산, 아비 위그더슨은 '''EXPTIME'''이 '''MA'''로 축소되지 않는 한, '''BPP'''가 i.o.-SUBEXP에 포함된다는 것을 보였다. i.o.-SUBEXP는 "무한히 자주 '''SUBEXP'''"를 의미하며, 무한히 많은 입력 크기에 대해 서브 지수 시간 알고리즘을 갖는 문제를 포함한다. 또한, 그들은 지수 시간 계층이 '''E^PH'''로 정의될 때 '''E'''로 축소되면 '''P''' = '''BPP'''임을 보였다. 그러나 지수 시간 계층은 일반적으로 축소되지 않을 것으로 추측된다.

러셀 임파글리아조와 아비 위그더슨은 '''E'''에 속하는 문제가 2^Ω(''n'')의 회로 복잡도를 가지면 '''P''' = '''BPP'''임을 증명했다.

5. 오라클 관련 성질

'''BPP'''는 보수에 대해 닫혀 있다. 즉, '''BPP''' = '''co-BPP'''이다. '''BPP'''는 자체적으로 low인데, 이는 '''BPP''' 문제를 즉시 해결할 수 있는 능력을 가진 '''BPP''' 머신 ('''BPP''' 오라클 머신)이 이 추가적인 능력이 없는 머신보다 더 강력하지 않다는 것을 의미한다. 기호로 나타내면, '''BPP'''^'''BPP''' = '''BPP'''이다.

오라클과 관련하여, P^A = BPP^A이고 P^B ≠ BPP^B인 오라클 A와 B가 존재한다.^[6] 또한, 확률 1로 임의 오라클과 관련하여 '''P''' = '''BPP'''이며 '''BPP'''는 NP와 co-NP에 엄격하게 포함된다.^[6]

심지어 BPP = EXP^NP (따라서 P < NP < BPP = EXP = NEXP)인 오라클도 존재한다.^[7]

참조

_[1] 간행물 CMPT 710 - Complexity Theory: Lecture 16 http://www.cs.sfu.ca[...] 2003-10-28
_[2] 간행물 Lecture 6: Randomized Algorithms, Properties of BPP http://people.csail.[...] Massachusetts Institute of Technology 2003-02-26
_[3] 웹사이트 Complexity Zoo:B - Complexity Zoo https://complexityzo[...]
_[4] 뉴스 Pulling Out The Quantumness http://weblog.fortno[...] 2005-12-20
_[5] 학술 Two theorems on random polynomial time
_[6] 학술 Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1
_[7] 학술 On relativized exponential and probabilistic complexity classes
_[8] 서적 Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman Springer
_[9] 학술 '''BPP''' has subexponential time simulations unless '''EXPTIME''' has publishable proofs
_[10] 학술 '''P''' = '''BPP''' if E requires exponential circuits: Derandomizing the XOR Lemma

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

문의하기 : help@durumis.com