일반 사례 복잡성

일반 사례 복잡성은 "대부분의 입력"에서 계산 문제의 복잡성을 연구하는 계산 복잡성 이론의 하위 분야다.

일반 사례 복잡성은 제시되지 않은 입력의 작은 세트를 무시하고 나머지 부분의 최악의 경우 복잡성을 고려함으로써 계산 문제의 복잡성을 측정하는 방법이다.소량은 점근밀도 측면에서 정의된다.일반적인 사례 복잡성의 명백한 효능은 다양한 콘크리트 계산 문제에서 가장 어려운 사례가 드물어 보이기 때문이다.전형적인 예는 비교적 쉽다.

복잡성에 대한 이러한 접근은 지난 세기 초로 거슬러 올라가는 계산적 전통을 가진 결합집단 이론에서 비롯되었다.일반적 복잡성의 개념은 2003년 논문에서 소개되었는데,^[1] 여기서 저자들은 정밀하게 생성된 다수의 집단에 대해 결합적 집단 이론, 즉 결합적 집단 이론, 결합적 문제, 구성원 문제라는 단어의 고전적 의사결정 문제의 일반적 시간 복잡성은 선형이라는 것을 보여주었다.

일반적인 사례 복잡성에 대한 자세한 소개는 설문 조사에서 확인할 수 있다.^[2][3]

기본 정의

점근밀도

내가 컴퓨터 문제에 대한 무한 입력 집합이 되게 하라.

정의 1.I의 크기 함수는 지도 ${\displaystyle \sigma }$: ${\displaystyle I\mathbb{}}$→ N ${\$:$무한$ 범위의 I$\to \mathb {N} }.$반지름 n의 공은 ${\displaystyle \mathrm{Bn}{}_{}}$=${\displaystyle }${ x ${\displaystyle \in }$ ${\displaystyle I\sigma }$(${\displaystyle }$x ) ${\displaystyle \le }$ n ${\displaystyle n}$ } } } $}$ {\$displaystyle B_{n}=\{x\in I\mid \sigma (x)\leq$ n$\}}}$이다$.$

입력이 유한한 알파벳에 걸쳐 문자열로 코드화된 경우, 크기는 문자열 길이일 수 있다.

$\{{\displaystyle {\mu n}_{}}$ ${\displaystyle \{\mu_{n}\}}}}$ ${\displaystyle {\mu n}_{}}$ ${\$은(는) ${\displaystyle {Bn}_{}}$ ${\$$displaystyle B_{n$$}}$에 대한 확률 분포인 확률 분포의 앙상블이 되도록$$$$ 한다$.$ $Bn{\displaystyle {}_{}}$$$ ${\$ B$}{n {\{n}{$n}}{n$}}}}.$가장 흔한 경우인 장비 분배정확히 많은$$${\displaystyle {Bn}_{}}$ ${\$B_${n$}s만 비어 있거나 ${\displaystyle {\mu n}_{}{Bn}_{}}$ ${\displaystyle {}_{}}$= ${\displaystyle 0}$ ${\displaystyle \mu _{n}(B_{n}=0})$이 있을 수 있다는 점에 유의하십시오$.$ 우리는 이러한 Bn을 무시한다.

정의 2.부분집합 $X{\displaystyle }$ ${\displaystyle \subset }$ ${\displaystyle I}$ ${\displaystyle X\subset$ I$}$의 점근 밀도는 이 한도가 존재할 때$$ $\rho {\displaystyle }$( ${\displaystyle \underset{}{X}}$) =${\displaystyle \underset{}{im}}$ n${\displaystyle \underset{}{}}$→${\displaystyle \underset{}{\mathrm{}}{\mu n}_{}}$($X$ )${\displaysty \rho$ (X$)=\lim \to \infto }\$mu $_{n}(X\cap B_{n}).$

공 ${\displaystyle {Bn}_{}}$ ${\$가 유한하고$$ ${\displaystyle {\mu n}_{}}$ ${\$가 장착 가능한 측정값일$$ 때,

${\displaystyle \rho (X)=\lim {\frac {X\cap B_{n}}{B_{n}}}}$

In this case it is often convenient to use spheres ${\displaystyle I_{n}=\{x\in I\mid \sigma (x)=n\}}$ instead of balls and define ${\displaystyle \rho '(X)=\lim {\frac { X\cap I_{n} }{ I_{n} }}}$. An argument using Stolz theorem shows that $$${\displaystyle \rho }$( ${\displaystyle X}$) ${\displaystyle \rho (X)}$이(${\displaystyle 가}$)${\displaystyle {}^{}}\rho {\displaystyle {}^{}}$ (${\displaystyle }$X${\displaystyle )}$ ${\displaystyle \rho '(X)}$이(가) 있는 경우$$, 이 경우에는 동일하다.

Definition 3 ${\displaystyle X\subseteq I}$ is generic if ${\displaystyle \rho (X)=1}$ and negligible if ${\displaystyle \rho (X)=0}$. X is exponentially (superpolynomially) generic if the convergence to the limit in Definition 2 is exponentially (superpolynomially) fast, etc.

일반적인 부분집합 X는 점증적으로 크다.실제로 X가 크게 나타나는지는 ${\displaystyle \mathrm{\mu n}{}_{}}$( X ${\displaystyle \cap }$ ${\displaystyle B_{}}$ n${\displaystyle {}_{}}$) ${\displaystyle \mu _{n}(X\cap B_{n})$이 1로 수렴되는$$ 속도에 따라 달라진다.초다항식 융합은 충분히 빠른 것 같다.

일반 복잡도 클래스

정의 4 알고리즘이 잘못된 답을 주지 않고 일반적인 입력 집합에서 다항 시간 내에 정답을 제공하는 경우 GenP(일반적으로 다항식 시간)에 있다.문제는 GenP에서 GenP의 알고리즘을 인정할 경우 입니다.GenL(일반적으로 선형 시간), GenE(선형 지수를 갖는 일반 지수 시간) GenExp(일반적으로 지수 시간) 등에 대해서도 동일하다.ExpGenP는 관련 제네릭 세트가 기하급수적으로 제네릭인 GenP의 하위 클래스다.

보다 일반적으로 $f{\displaystyle }$: ${\displaystyle N\mathbb{}}$→ ${\displaystyle N\mathbb{}}$ ${\$ f$:\mathb {N} \to \mathb {N}$에 대해 일반$$ 입력 집합에서 시간 복잡성 O(f)에 해당하는 클래스 Gen(f)을 정의할 수 있다.

정의 5.알고리즘은 오답이 없는 경우와 일반적인 입력 집합에 대해 정답을 제공하는 경우 일반적으로 문제를 해결한다.문제는 어떤 알고리즘에 의해 일반적으로 해결된다면 일반적으로 해결될 수 있다.

이론 및 응용

조합군 이론 문제

• 잘 알려지지 않은 유명한 문제들: 적절한 가설 아래, 단어, 결합 그리고 멤버쉽 결정 문제는 일반적으로 다항식이다.^[1]
• 단어와 결합 검색 문제는 모든 고정된 그룹들에 대해 GenP에 있다.^[4]

• 잘 알려진 코제트 열거 절차는 일반적인 입력 집합에서 계산 가능한 상한을 허용한다.^[5]

• 자유 그룹의 한 요소가 자동형성에 의해 다른 요소에 매핑되는지 여부를 테스트하기 위한 화이트헤드 알고리즘은 지수적으로 최악의 경우 상한선을 가지고 있지만 실제로 잘 실행된다.알고리즘은 GenL로 표시된다.^[6]

• HNN 확장의 결합 문제는 무료 그룹에서도 해결할 수 없다.그러나, 그것은 일반적으로 입방 시간이다.^[7]

중지 문제와 사후 대응 문제

• 단면 테이프가 있는 튜링 기계의 정지 문제는 대부분 쉽게 해제할 수 있다; 그것은 GenP에^[8] 있다.

양면테이프의 상황은 알 수 없다.그러나 두 종류의 기계에는 일종의 하한선이 있다.정지 문제는 튜링 기계의 어떤 모델에 대해서도 ExpGenP에 있지 않다.^[9][10]

• 포스트 서신 문제는 ExpGenP에 있다.^[2]

프레스버거 산술

Presburger 산술의 결정 문제는 이중 지수 하한과^[11] 삼중 지수 하한선을 인정한다.일반적인 복잡성은 알려져 있지 않지만 문제는 ExpGenP에 있지 않은 것으로 알려져 있다.^[12]

NP 완료 문제

NP-완전한 문제가 평균적으로 쉬울 수 있다는 것은 잘 알려져 있기 때문에, 그 중 몇 가지 문제도 일반적으로 쉽다는 것은 놀라운 일이 아니다.

• 세 가지 만족도 문제는 ExpGenP에 있다.^[13]
• 부분집합 문제는 GenP에 있다.^[2]

단방향 기능

동일한 종류의 기능을 제공하지만 일반적과는 다른 보안 가정을 고려할 수 있는 단방향 함수의^[14] 일반적인 복잡성 버전이 있다.

공개키암호법

일련의 기사들은^[15][16][17] 안셀-안셀-골드펠트 키 교환 프로토콜의 암호화에 전념하고 있는데, 이 프로토콜의 보안은 브레이드 그룹에 관한 가정에 기초하고 있다.이 시리즈는 일반 사례 복잡성에서 기법을 적용하여 길이에 기초한 공격과 그것이 작용하는 조건에 대한 완전한 분석을 얻는 Miasnikov와 Ushakov(2008)^[18]에서 절정을 이룬다.일반적인 관점은 또한 지수의 공격이라고 불리는 일종의 새로운 공격과 안셀-안셀-골드펠트 프로토콜의 보다 안전한 버전을 시사한다.

일반 이론적 결과 목록

• 유명한 라이스의 정리는 $F$가 N ${\$부터${\displaystyle }${ ${\displaystyle 0,}$ 1 ${\displaystyle \}}$ ${\displaystyle \{0,1$까지 부분 계산 가능한 함수 집합의 하위 집합이라면 F나 그 보수가 비어 있지 않은 한 F에서 특정 튜링 시스템의 함수 계산 여부를 결정하는 문제는 불분명하다고 말한다.다음의 정리는 일반적인 버전을 제공한다.

정리 1^[19] 내가 모든 튜링 기계들의 집합이 되게 하라.F가 $N{\displaystyle \mathbb{}}${\$displaystyle \mathb{N}$에서 F와 그 보완물이 모두 비어 있지 않은 그 자체로$$ 모든 부분 계산 가능한 함수 집합의 부분 집합인 경우, 주어진 튜링 시스템이 F에서 함수를 계산하는지 여부를 결정하는 문제는 기하급수적으로 일반적인 I의 어떤 부분 집합에서도 취소할 수 없다.

• 다음과 같은 이론은 다음과 같다.^[1]

정리 2 일반적으로 계산할 수 있는 공식 언어 집합은 0을 측정한다.

정리 3 일반적인 복잡성 등급의 무한한 계층이 있다.적절한 복잡도 함수 f, $G{\displaystyle }$ ${\displaystyle e}$ ${\displaystyle n}$( f${\displaystyle }$) ${\displaystyle ⊊}$ G ${\displaystyle e}$ ${\displaystyle n}$( ${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$) ${\displaystyle Gen(f)\subsetneq Gen(f^{3})}$을(를) 보다 정확하게$.$

• 다음 정리는 분포 NP 문제 내에 평균적인 사례 완결 문제가 있는 것처럼,

또한 일반적인 사례 전체 문제들이 있다.일반 사례의 주장은 평균 사례의 주장과 유사하며, 일반 사례 완료 문제도 평균 사례 완료다.그것은 유통 경계선인 중지 문제야.

정리 4^[2] 분포 NP 문제의 종류 내에서 분포 경계 중단 문제가 완료되는 것과 관련하여 일반-폴리놈 시간 단축의 개념이 있다.

이전 작품과의 비교

거의 다항식 시간

Meyer와 Paterson은^[20] 알고리즘이 크기 n의 p(n) 입력을 제외한 모든 입력에서 p(n) 단계 내에서 정지하는 경우 거의 다항식 시간 또는 APT로 정의한다.분명히 APT 알고리즘은 우리 클래스 GenP에 포함되어 있다.우리는 GenP에서 NP완전 문제를 여러번 보았지만, 마이어와 패터슨은 APT의 경우는 그렇지 않다는 것을 보여준다.그들은 P = NP인 경우에만 APT의 문제로 NP 완전 문제가 축소될 수 있음을 증명한다.그러므로 APT는 GenP보다 훨씬 더 제한적인 것처럼 보인다.

평균 사례 복잡성

일반적인 사례 복잡성은 평균 사례 복잡성과 유사하다.그러나 몇 가지 유의미한 차이가 있다.일반적인 사례 복잡성은 대부분의 입력에서 알고리즘의 성능을 직접 측정하는 반면, 평균 사례 복잡성은 쉬운 경우와 어려운 경우 사이의 균형을 측정한다.또한 일반 사례의 복잡성은 자연적으로 이해할 수 없는 문제에 적용된다.

${\$이(가) 시간 복잡성을 갖는 $알고리즘$이라고 가정해$$ 보십시오. T${\displaystyle }$: ${\displaystyle I}$→ ${\displaystyle N\mathbb{}}$ ${\$$I\to \mathb {N}은($는) $\mu {\displaystyle }$ ${\displaystyle \mu }$ 평균의$$ 다항식이다$$.일반적인 입력에 대한$$ $A{\displaystyle \mathcal{}}$ ${\$의 동작에 대해 유추할 수 있는 것은?

Example 1 Let I be the set of all words over ${\displaystyle \{0,1\}}$ and define the size ${\displaystyle \sigma (w)}$ to be word length, ${\displaystyle w }$. Define ${\displaystyle I_{n}}$ to be the set of words of length n, and assume that each ${\displaystyle \mu _{n}}$장비 가능한 척도.예외적인 단어에 대해$$ $각{\displaystyle {}_{}}$ ${\displaystyle {In}_{}}$ ${\$및 $T{\displaystyle (w}$) = 2 ${\displaystyle {{2n}^{}}^{}}$ ${\$을(를) 제외한 모든 단어에 대해 T(w)=n이라고 가정해 보십시오.

이 예제에서 T는 전형적인 입력에서는 확실히 다항식이지만, T는 평균적으로 다항식이 아니다.T는 GenP에 있다.

Example 2 Keep I and ${\displaystyle \sigma (w)= w }$ as before, but define ${\displaystyle \mu (w)=2^{-2 w -1}}$ and ${\displaystyle T(w)=2^{ w }}$. T is polynomial on average even though it is exponential on typical inputs.T는 GenP에 있지 않다.

이 두 예에서 일반적인 복잡성은 평균 사례 복잡성보다 일반적인 입력의 동작과 더 밀접하게 관련되어 있다.평균적인 사례 복잡성은 다른 것을 측정한다: 어려운 경우의 빈도와 난이도 사이의 균형.^[21][22]평균적으로 다항식 시간인 알고리즘은 계산에 초항식 시간이 필요한 입력의 소환수 비율만 가질 수 있다.

그럼에도 불구하고 경우에 따라서는 일반적이고 평균적인 사례 복잡성이 상당히 서로 밀접한 경우도 있다.$함수{\displaystyle }$ f${\displaystyle }$: ${\displaystyle I}$→ ${\displaystyle {}^{}}$+ ${\$$I\rightarrow \mathbb {R} ^{+}}$ is polynomial on ${\displaystyle \mu }$-average on spheres if there exists ${\displaystyle k\geq 1}$ such that ${\displaystyle \sum _{w\in I_{n}}f^{1/k}(w)\mu _{n}(w)=O(n)}$ where ${\displaystyle \{\mu _{n}\}}$$[\displaystyle$\$mu{\displaystyle }$ $}$에 의해 유도된 앙상블이다. f가 μ에 다항식인 경우 ${\displaystyle \mu }$ - 평균인$$$$ 경우, f는 $\mu$에 다항식이고, 많은 분포에 대해 역이 가지고 있다.

정리 5^[2] 함수 $f{\displaystyle }$: ${\displaystyle {\mathbb{}}^{}}$→ R${\displaystyle {}^{}}$+ ${\$$I\rightarrow \mathb {R} ^{+}$ $\mu$에 다항식인 $\displaystyle \mu }$ - 구에서 평균인$$ 다음 f는 구면 점근밀도 ${\$에 상대적인 다항식이다$.$

도 이와 같은 문제 ExpGenP의 앙상블{nμ}에 대하여{\displaystyle\와 같이{\mu_{n}\은 정리 6[2] 완전한 알고리즘{\displaystyle{{A\mathcal}}}}}}는인 확률 측정 μ{년에 해당하는subexponential 시간을 묶고 티 셔츠와 부분적인 알고리즘 B{\displaystyle{{B\mathcal}}을 가지고 있다.경멸하다$입력{\displaystyle \mathcal{}}$ I ${\$에 대한 $playstyle \mu$$\}.$ 그러면 $\mu {\displaystyle }$ ${\displaystyle \mu}$ - 평균$$ 시간 복잡도인 전체 알고리즘이 있다.

오류 없는 경험적 경험적 알고리즘

2006년 논문에서 보그다노프와 트레비산은 일반적인 사례 복잡성을 정의하는데 근접했다.^[24]부분 알고리즘 대신 이른바 오류 없는 휴리스틱 알고리즘을 고려한다.이것들은 출력 "?"로 정지함으로써 실패할 수 있는 완전한 알고리즘이다.클래스 AvgnegP는 다항식으로 실행되며 ${\displaystyle {In}_{}}$ ${\$에서 고장 확률은 무시할 수$$ 있는 모든 무오류적 경험적 알고리즘 A로 구성된다. 즉, 초공칭적으로 빠르게 0으로 수렴한다.AvgnegP는 GenP의 하위집합이다.오류 없는 경험적 경험적 알고리즘은 임파글리아조에 의해 정의된 양성 결함을 가진 알고리즘과 본질적으로 동일하며, 여기서 평균 알고리즘의 다항식 시간이 소위 양성 알고리즘 체계로 특징지어진다.

참조