평균 케이스의 복잡성

계산 복잡도 이론에서, 알고리즘의 평균적인 경우 복잡도는 알고리즘에 의해 사용되는 일부 계산 자원의 양(일반적으로 시간)으로, 가능한 모든 입력에 대해 평균이 됩니다.이는 가능한 모든 입력에 대해 알고리즘의 최대 복잡성을 고려하는 최악의 경우 복잡성과 자주 대비됩니다.

평균 사례의 ^[1]복잡성을 연구하는 데는 세 가지 주요 동기가 있습니다.첫째, 비록 몇몇 문제들이 최악의 경우 다루기 어려울 수 있지만, 이러한 행동을 유도하는 입력은 실제로 거의 발생하지 않을 수 있으므로, 평균 사례 복잡도는 알고리즘의 성능을 더 정확하게 측정할 수 있다.둘째, 평균 사례 복잡도 분석은 암호화 및 디랜덤화 등의 영역에서 활용할 수 있는 문제의 하드 인스턴스를 생성하기 위한 도구와 기술을 제공합니다.셋째, 평균 케이스 복잡도를 통해 동등한 베스트 케이스 복잡도의 알고리즘(예: QuickSort) 중에서 실제로 가장 효율적인 알고리즘을 식별할 수 있습니다.

평균 사례 분석을 위해서는 알고리즘에 대한 "평균" 입력의 개념이 필요하며, 이는 입력에 대한 확률 분포를 고안하는 문제로 이어집니다.또는 랜덤화 알고리즘을 사용할 수 있다.이러한 알고리즘의 분석은 예상되는 ^{[2]: 28} 복잡성의 관련 개념으로 이어진다.

이력 및 배경

알고리즘의 평균 사례 성능은 1950년대에 계산 효율의 현대적 개념이 개발된 이후 연구되어 왔다.이 초기 작업의 대부분은 최악의 다항 시간 알고리즘이 이미 ^[3]알려진 문제에 초점을 맞췄다.1973년 도널드^[4] 크누스는 정렬과 중위수 찾기 등 최악의 다항 시간에 해결 가능한 문제에 대한 알고리즘의 평균 사례 성능을 광범위하게 조사하는 컴퓨터 프로그래밍 기술 제3권을 출판했다.

NP-완전 문제에 대한 효율적인 알고리즘은 일반적으로 모든 입력에 대해 다항식 시간으로 실행되는 알고리즘으로 특징지어집니다. 이는 효율적인 최악의 경우 복잡성을 요구하는 것과 같습니다.그러나 "작은" 입력 수로 비효율적인 알고리즘은 실제로 발생하는 "대부분" 입력에 대해 여전히 효율적일 수 있습니다.따라서 평균 사례 복잡도가 최악의 경우 복잡도와 다를 수 있는 이러한 알고리즘의 특성을 연구하고 이 둘을 관련짓는 방법을 찾는 것이 바람직하다.

평균 사례 복잡성의 기본 개념은 1986년 레오니드 레빈이 NP의 평균 사례 유사체인 distNP에 대한 완전한 문제의 예를 제시하면서 평균 사례 복잡성과 완전성을 정의하는 1페이지^[5] 분량의 논문을 발표하면서 개발되었다.

정의들

효율적인 평균 케이스의 복잡성

첫 번째 작업은 "평균적으로" 효율적인 알고리즘이 무엇을 의미하는지 정확하게 정의하는 것입니다.첫 번째 시도에서는 모든 가능한 입력에 걸쳐 예상되는 다항식 시간에 실행되는 효율적인 평균 사례 알고리즘을 정의할 수 있습니다.그러한 정의는 다양한 단점을 가지고 있다; 특히, 계산 모델의 변경에 강하지 않다.예를 들어, 알고리즘 A가 입력 x의 시간_A t(x)에서 실행되고 알고리즘 B가 입력 x의 시간_A t(²x)에서 실행된다고 가정합니다. 즉, B가 A보다 2차적으로 느립니다.직관적으로 평균 사례 효율성의 정의는 B가 평균 효율적일 경우에만 A가 평균 효율적이라는 생각을 포착해야 한다.단, $입력$이 길이가n(\$displaystyle$ n$)$인 문자열의 균일한 분포에서 랜덤하게 추출되어 A가 시간2가ⁿ 걸리는 문자열1을ⁿ 제외한 모든 입력에서 시간n으로² 실행된다고 가정합니다.그러면 A의 예상 실행 시간은 다항식이지만 B의 예상 실행 시간은 ^[3]기하급수적인지 쉽게 확인할 수 있습니다.

평균 케이스 효율의 보다 견고한 정의를 작성하려면 알고리즘 A가 일부 입력에서 다항식 시간보다 더 오래 실행되도록 허용하는 것이 타당하지만 A가 점점 더 큰 실행 시간을 필요로 하는 입력의 비율은 점점 더 작아집니다.이 직관은 평균 다항식 실행 시간에 대한 다음 공식에서 포착되며, 실행 시간과 입력 비율 사이의 다항식 트레이드오프를 균형 있게 조정합니다.

$\displaystyle \Pr_{x\in_{R}D_{n}\left[t_{A}(x)\geq t\right]\leq {p(n)}{t^{\epsilon }}}}$

n마다 t > 0 및 다항식 p에 대해 t(x_A)는 입력 x에 대한 알고리즘 A의 실행 시간을 나타내고 θ는 양의 상수 ^[6]값입니다.또는 다음과 같이 쓸 수 있습니다.

${\displaystyle E_{x\in_{R}D_{n}}\left[{\frac {t_{A}(x)^{\epsilon}}{n}}\right]\leq C}$

일부 상수 C 및 상수 = x(n = x).^[7] 즉, t(n) 스텝을_A 실행한 후 A가 $n{\displaystyle \frac{{}^{}}{}}$ ${\displaystyle \frac{c^{}}{}}$ ${\displaystyle \frac{{}_{}A{}^{}}{}}$(${\displaystyle \frac{}{}}$n )${\displaystyle \frac{{ϵ}^{}}{}}$ \ $display$style \ $frac${ $n$^ { c } { ( $t$_ { $A （$$n$ ) $}$ { ( t _ { A （ n ) ） 。$^{\silon$}}}}: 길이n$$ 입력의 분수(일부 θ, c > 0).^[3]

배포 문제

다음 단계는 특정 문제에 대한 "평균" 입력을 정의하는 것입니다.이것은 각 문제의 입력을 특정 확률 분포와 연관시킴으로써 달성됩니다.즉, "평균 사례" 문제는 언어 L과 쌍을 형성하는 관련 확률 분포 D로 구성됩니다(L, D).^[7]허용되는 가장 일반적인 두 가지 배포 클래스는 다음과 같습니다.

1. Polynomial-time 계산할 수 있는 분포(P-computable):이 분배에 x. 더 공식적으로 어떤 주어진 입력의 누적된 밀도를 계산하기 위해, 확률 분포 μ와 문자열)∈{0,1}n 그것 μ())은 값을 계산하는 데)가능하다 ∑ y∈ n:y{0,1}≤)Pr[y]{\displaystyle \mu 가능하다. ($x)=\sum \sum$ _${y\in$\{$0,1\}^{n:y\leq$ x$}\Pr[y]}$ 다항식$$ 시간$.$이것은 Pr[x]도 다항식 시간으로 계산할 수 있다는 것을 의미한다.
2. 다항식 시간 표본 추출 가능 분포(P-표본): 다항식 시간에 랜덤 표본을 추출할 수 있는 분포입니다.

이 두 공식은 비슷하지만 동일하지 않습니다.분포가 P-계산 가능한 경우 P-샘플링도 가능하지만 P p^{#P [7]}P이면 그 반대가 성립하지 않습니다.

평균값과 디스트NP

위에서 정의한 바와 같이 L의 효율적인 평균 케이스알고리즘이 존재하는 경우, 분산 문제(L, D)는 복잡도 클래스의 AvgP에 있습니다.문헌에서는 클래스 AvgP를 ^[7]distP라고 부르기도 합니다.

분포 문제(L, D)가 복잡도 클래스 dist에 있습니다.L이 NP에 있고 D가 P-계산 가능한 경우 NP.L이 NP에 있고 D가 P 샘플링 가능한 경우, (L, D)는 samp에 속합니다.NP.^[7]

AvgP와 디스트의 조합NP 는,^[7] 각각 P 와 NP 의 평균 대소문자 유추를 정의합니다.

배포 문제 간의 감소

(L,D)와 (L',D')를 2개의 분포 문제로 하자. (L,D) 평균 대소문자는 (L,D')로 감소한다 (L,D) (_AvgP (L',D') 만약 n마다 f가 존재한다면 입력 x는 n의 다항식 시간으로 계산될 수 있다.

1. (정확성) x l L(f(x) l L'인 경우만
2. (지배력)모든 n과 y에 대해${\displaystyle \underset{}{}}$θ${\displaystyle \underset{}{x}}$ :${\displaystyle \underset{}{f}}$ (${\displaystyle \underset{}{x}}$ ) $=$ ${\displaystyle \underset{}{y}}$ ${\displaystyle \underset{}{}{}_{}{n}_{}}$ (${\displaystyle x}$ )${\displaystyle p}$p (${\displaystyle n}$ ) ${\displaystyle {}_m^{}}$ (${\displaystyle n_{}^{}}$ ) ${\displaystyle (}$($$ ) \ $displaystyle \sum \sum$ _${x:f(x$)=$y} D_{n}(x)\leq$p($n) D'y(n)$가 되는 다항식이 있다.

지배조건은 문제(L, D)가 평균적으로 어렵다면 (L', D')도 평균적으로 어렵다는 개념을 강요한다.직관적으로, 감소는 f(x)를 계산하고 출력을 L'을 푸는 알고리즘에 공급함으로써 문제 L의 인스턴스 x를 해결하는 방법을 제공해야 한다.지배조건이 없으면 평균적으로 L을 다항시간으로 푸는 알고리즘은 소수의 입력에 대해 초다항시간이 걸리지만 f는 알고리즘 A'가 평균 다항시간에서 더 이상 실행되지 않도록 이들 입력을 훨씬 더 큰 집합의 D'에 매핑할 수 있기 때문에 이것이 불가능할 수 있다.지배조건은 이러한 문자열이 D'^[6]에서 자주 다항식으로만 발생하는 것을 허용한다.

DistNP-완전한 문제

NP 완전성에 대한 평균 케이스의 아날로그는 distNP 완전성입니다.분포 문제(L', D')는 (L', D')가 dist NP-complete인 경우NP 및 distNP의 모든 (L, D)에 대해 (L, D)는 (L', D')^[7]로 평균 대소문자 환산할 수 있다.

디스트의 예NP-완전 문제는 다음과 같이 정의된 유계 정지 문제 BH입니다.

BH = {(M,x,1^t) : M은 비논리적인 튜링 기계로, x를 δT 단계로 받아들인다.}^[7]

레빈은 원본 논문에서 평균 사례 ^[5]NP-완전인 분포 타일링 문제의 예를 보여 주었다.알려진 distNP-complete 문제에 대한 조사는 온라인으로 제공됩니다.^[6]

활발한 연구의 한 분야에는 새로운 distNP-완전 문제를 찾는 것이 포함됩니다.그러나 이러한 문제점을 찾아내는데 Gurevich의지 않는 한 미국)NEXP.[8]ε ≤ 2−)(공평한 분배 μ은에는 ε 을이 존재한다;0이 어떤 x에, μ())이 평평한 유통과 분포 상의 문제distNP-complete 수 없음을 보여 준 결과 때문에.)Livne에 의한 결과 모든 천연 NP-완전을 보여 주복잡할 수 있다. 문제 have DistNP-complete 버전.^[9]그러나 DistNP-완전한 자연분포 문제를 찾는 목표는 아직 ^[10]달성되지 않았다.

적용들

정렬 알고리즘

위에서 언급했듯이, 평균 사례의 복잡성과 관련된 많은 초기 연구는 정렬과 같은 다항 시간 알고리즘이 이미 존재하는 문제에 초점을 맞췄다.예를 들어 Quicksort 등 랜덤성을 이용하는 정렬 알고리즘의 대부분은 최악의 경우 실행시간이 O(n²)이지만 평균 실행시간은 O(nlog(n)입니다.여기서 n은 정렬되는 ^[2]입력의 길이입니다.

암호화

대부분의 문제의 경우, 평균 사례 복잡도 분석은 최악의 경우 어렵다고 간주되는 문제에 대한 효율적인 알고리즘을 찾기 위해 수행된다.그러나 암호화 어플리케이션에서는 그 반대입니다.최악의 복잡성은 무관합니다.대신 암호화 스킴을 '파괴'하는 모든 알고리즘의 평균적인 복잡성이 ^[11]비효율적이라는 보증을 원합니다.

따라서 모든 보안 암호화 방식은 단방향 ^[3]함수의 존재에 의존합니다.단방향 함수의 존재는 여전히 미해결 문제이지만, 많은 후보 단방향 함수는 정수 인수분해나 이산 로그 계산과 같은 어려운 문제에 기초하고 있습니다.후보 함수가 NP-완전인 것은 바람직하지 않습니다.이는 최악의 경우 문제를 해결하기 위한 효율적인 알고리즘이 존재하지 않을 가능성이 높기 때문입니다.우리가 실제로 원하는 것은 어떤 효율적인 알고리즘도 랜덤 입력(평균적인 경우)에 대해 문제를 해결할 수 없다는 보증입니다.실제로 정수 인수분해와 이산 로그 문제는 모두 NP ≤ coNP이므로 ^[7]NP-완전하다고 생각되지 않습니다.모든 암호학이 NP에 평균 케이스의 난해한 문제의 존재를 전제로 하고 있다는 사실은 평균 케이스의 복잡성을 연구하기 위한 주요 동기 중 하나이다.

기타 결과

1990년에, Impaglizzo와 Levin은 만약 디스트에 대한 효율적인 평균 사례 알고리즘이 있다면균일한 분포에서 NP-완전 문제는 다항식 시간 샘플링 가능한 ^[12]분포에서 NP의 모든 문제에 대한 평균 사례 알고리즘이 있습니다.이 이론을 자연 분포 문제에 적용하는 것은 여전히 미해결의 ^[3]문제로 남아 있다.

1992년, 벤 데이비드 외 연구진은 만약 모든 언어들이 원형을 이룬다면NP는 평균적인 결정 알고리즘과 평균적인 검색 알고리즘이 있습니다.게다가 이러한 결론은, NP의 모든 언어가 균일한 분포에 관해서 결정 알고리즘에 대해서 평균적으로 쉬운 경우, 균일한 ^[13]분포에 관해서도 검색 알고리즘에 대해서 평균적으로 쉬운 것이라는 보다 약한 가정에 근거하고 있는 것을 나타내고 있다.따라서 암호 단방향 함수는 다음과 같은 경우에만 존재할 수 있습니다.결정 알고리즘에서는 평균적으로 어려운 균일한 분포에 대한 NP 문제.

1993년에 Feigenbaum과 Fortnow는 비적응적 무작위 감소 하에서 디스트에 대한 평균적인 알고리즘의 존재를 증명할 수 없음을 보여주었다.균일한 분포에서의 NP-완전 문제는 ^[14]NP의 모든 문제에 대해 최악의 경우 효율적인 알고리즘이 존재함을 의미합니다.2003년에 Bogdanov와 Trevisan은 이 결과를 임의의 비적응적 ^[15]감소로 일반화했다.이러한 결과는 ^[3]감소를 통해 평균 사례의 복잡성과 최악의 경우 복잡성 사이의 연관성을 만들 수 없다는 것을 보여준다.

「 」를 참조해 주세요.

• 알고리즘의 확률론적 분석
• NP-완전 문제
• 최악의 경우 복잡성
• 상각분석
• 베스트, 워스트, 평균 케이스

레퍼런스

추가 정보

사례의 평균 복잡성에 관한 문헌에는 다음과 같은 작업이 포함되어 있습니다.

• 를 클릭합니다Franco, John (1986), "On the probabilistic performance of algorithms for the satisfiability problem", Information Processing Letters, 23 (2): 103–106, doi:10.1016/0020-0190(86)90051-7.
• 를 클릭합니다Levin, Leonid (1986), "Average case complete problems", SIAM Journal on Computing, 15 (1): 285–286, doi:10.1137/0215020.
• 를 클릭합니다Flajolet, Philippe; Vitter, J. S. (August 1987), Average-case analysis of algorithms and data structures, Tech. Report, Institut National de Recherche en Informatique et en Automatique, B.P. 105-78153 Le Chesnay Cedex France.
• 를 클릭합니다Gurevich, Yuri; Shelah, Saharon (1987), "Expected computation time for Hamiltonian path problem", SIAM Journal on Computing, 16 (3): 486–502, CiteSeerX 10.1.1.359.8982, doi:10.1137/0216034.
• 를 클릭합니다Ben-David, Shai; Chor, Benny; Goldreich, Oded; Luby, Michael (1989), "On the theory of average case complexity", Proc. 21st Annual Symposium on Theory of Computing, Association for Computing Machinery, pp. 204–216.
• 1989년 초안도 참조Gurevich, Yuri (1991), "Average case completeness", Journal of Computer and System Sciences, 42 (3): 346–398, doi:10.1016/0022-0000(91)90007-R, hdl:2027.42/29307.
• 를 클릭합니다Selman, B.; Mitchell, D.; Levesque, H. (1992), "Hard and easy distributions of SAT problems", Proc. 10th National Conference on Artificial Intelligence, pp. 459–465.
• 를 클릭합니다Schuler, Rainer; Yamakami, Tomoyuki (1992), "Structural average case complexity", Proc. Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 652, Springer-Verlag, pp. 128–139.
• 를 클릭합니다Reischuk, Rüdiger; Schindelhauer, Christian (1993), "Precise average case complexity", Proc. 10th Annual Symposium on Theoretical Aspects of Computer Science, pp. 650–661.
• 를 클릭합니다Venkatesan, R.; Rajagopalan, S. (1992), "Average case intractability of matrix and Diophantine problems", Proc. 24th Annual Symposium on Theory of Computing, Association for Computing Machinery, pp. 632–642.
• 를 클릭합니다Cox, Jim; Ericson, Lars; Mishra, Bud (1995), The average case complexity of multilevel syllogistic (PDF), Technical Report TR1995-711, New York University Computer Science Department.
• 를 클릭합니다Impagliazzo, Russell (April 17, 1995), A personal view of average-case complexity, University of California, San Diego.
• Paul E. Black, 알고리즘 및 데이터 구조 사전 [온라인]의 "II"Paul E. Black, ed., 미국 국립표준기술연구소2004년 12월 17일2009년 2월 20일 취득.
• Christos Papadimitriou (1994년).계산의 복잡성애디슨 웨슬리.