유니크 게임 추측

계산 복잡성 이론에서, 독특한 게임 추측(흔히 UGC라고 불림)은 2002년 Subhash Khot에 의해 만들어진 추측이다.^[1][2][3]독특한 게임으로 알려진 특정 유형의 게임의 대략적인 가치를 결정하는 문제는 NP-하드 계산 복잡성을 가지고 있다고 추측한다.근사치 경도 이론에 광범위하게 응용되어 있다.만약 독특한 게임 추측과 P and NP가 사실이라면,^[4] 많은 중요한 문제들에 대해 다항 시간(P 대 NP 문제로 가정된 바와 같이)에서 정확한 해결책을 얻는 것은 불가능할 뿐만 아니라, 좋은 다항 시간 근사치를 얻는 것도 불가능하다.그러한 비교가능성 결과가 안고 있는 문제에는 제약조건 만족도 문제가 포함되며, 이는 다양한 분야에서 발생한다.

사실 여부를 놓고 학계가 엇비슷하게 갈리는 것 같다는 점에서 추측이 이례적이다.^[1]

공식화

독특한 게임 추측들은 여러 가지 동등한 방법으로 진술될 수 있다.

유니크 라벨 커버

독특한 게임 추측의 다음과 같은 공식은 근사치 경도에 종종 사용된다.이 추측은 라벨 커버로 알려진 다음과 같은 약속 문제의 NP-강성을 고유한 제약조건으로 가정한다.각 가장자리에서, 두 꼭지점의 색상은 특정한 순서 쌍으로 제한된다.고유 제약조건은 각 에지에 대해 순서가 지정된 쌍 중 동일한 노드에 대해 동일한 색상을 갖는 쌍이 없음을 의미한다.

즉, 크기 k의 알파벳에 걸쳐 고유한 제약 조건을 가진 라벨 커버의 인스턴스를 그래프의 각 에지 e에 대해 각각 하나씩 순열 perm_e: [k] → [k]의 집합과 함께 지시된 그래프로 나타낼 수 있다.라벨 표지 인스턴스에 대한 할당은 G의 각 꼭지점에 집합 [k] = {1, 2, ...k}의 값을 부여하며, 흔히 "컬러"라고 불린다.

• 

  고유한 레이블 커버의 인스턴스.4개의 꼭지점에는 빨간색, 파란색 및 녹색의 색상이 할당될 수 있으며 각 가장자리의 구속조건을 충족할 수 있다.

• 

  고유한 레이블 커버 인스턴스에 대한 솔루션.

그러한 예는 꼭지점의 색상이 이웃의 색상을 고유하게 정의한다는 점에서, 그리고 따라서 그 연관된 전체 구성요소에 대해 강하게 제한된다.따라서 입력 인스턴스가 유효한 할당을 허용하는 경우, 그러한 할당을 단일 노드의 모든 색상에 반복함으로써 효율적으로 찾을 수 있다.특히 주어진 사례가 만족스러운 과제를 인정하는지를 결정하는 문제는 다항 시간 내에 해결할 수 있다.

• 

  만족스러운 할당을 허용하지 않는 고유한 레이블 커버의 인스턴스.

• 

  두꺼운 가장자리를 제외한 모든 가장자리를 만족시키는 할당.따라서 이 인스턴스의 값은 3/4이다.

고유한 라벨 커버 인스턴스의 값은 할당으로 충족될 수 있는 제약 조건의 비율이다.만족스러운 경우 이 값은 1이며 쉽게 찾을 수 있다.반면에, 대략적으로라도, 만족스럽지 못한 게임의 가치를 결정하는 것은 매우 어려워 보인다.독특한 게임들은 이러한 어려움을 공식화한다.

보다 공식적으로, 고유한 제약조건이 있는 (c, s)갭 라벨 커버 문제는 다음과 같은 약속 문제(L_yes, L_no)이다.

• L_yes = {G: 일부 할당은 G}에서 제약 조건의 c-fraction을 최소한 충족함
• L_no = {G: 모든 할당은 G}에서 제약 조건의 s-fraction을 최대로 만족한다.

여기서 G는 고유한 제약조건이 있는 라벨 커버 문제의 한 예다.

고유 게임 추측에 따르면, 충분히 작은 상수 0, Δ > 0의 모든 쌍에 대해 (1 - Δ, Δ)-갭 라벨 커버 문제가 존재하며, 크기 k의 알파벳에 대한 고유한 제약조건이 있다.P-hard라고 한다.

그래프 대신 레이블 표지 문제는 선형 방정식으로 공식화할 수 있다.예를 들어, 정수 모듈로 7에 대한 선형 방정식의 시스템이 있다고 가정합시다.

${\displaystyle {\begin{aligned}x_{1}&\equiv 2\cdot x_{2}{\pmod {7}},\\x_{2}&\equiv 4\cdot x_{5}{\pmod {7}},\\&{}\ \ \vdots \\x_{1}&\equiv 2\cdot x_{7}{\pmod {7}}.\end{정렬}}}$

이것은 고유한 제약조건이 있는 라벨 커버 문제의 한 예다.예를 들어 첫 번째 방정식은 순열 perm에_{(1, 2)} 해당하며_{(1, 2)1} 여기서 mod(x) = 2x₂ modulo 7이다.

2-프로버 프루프 시스템

독특한 게임은 2프로버 원라운드(2P1R) 게임의 특별한 경우다.2프로 1회전 경기는 두 명의 선수(일명 프로버)와 심판이 있다.심판은 알려진 확률 분포에서 도출된 질문을 선수마다 보내고, 선수들은 각자 답을 보내야 한다.정답은 고정된 크기의 집합에서 나온다.경기는 선수들에게 보내는 질문과 선수들에 의해 제공되는 답변에 따라 달라지는 술어로 지정된다.

선수들은 경기 중에 서로 의사소통을 할 수는 없지만 미리 전략을 결정할 수도 있다.술어가 자신의 질문과 대답에 만족하면 선수들은 승리한다.

1번 선수의 모든 질문과 대답에 대해 두 번째 선수의 답이 정확히 한 개씩 있다면, 2번 선수의 1회전 게임은 독특한 게임이라고 불린다.게임의 가치는 모든 전략에 대한 선수들의 최대 승리 확률이다.

독특한 게임 추측에 따르면 상수 constants, Δ > 0의 모든 작은 쌍에 대해 다음과 같은 약속 문제(L_yes, L_no)가 NP-hard일 정도로 상수 k가 존재한다고 한다.

• L_yes = {G: G 값이 최소 1 - Δ}임
• L_no = {G: G 값은 최대 most}

여기서 G는 k사이즈 세트에서 답이 나오는 독특한 게임이다.

확률적으로 확인할 수 있는 증거

또는, 독특한 게임 추측이 NP의 문제에 대해 확률적으로 확인할 수 있는 특정 유형의 증거가 존재한다고 가정한다.

독특한 게임은 질의 복잡성 2와 함께 비적응 확률적으로 확인할 수 있는 특별한 종류의 증거로 볼 수 있다. 여기서 검증자의 가능한 질의의 각 쌍과 첫 번째 질의에 대한 각각의 가능한 답변에 대해 검증자가 수용하게 하는 두 번째 질의에 대해 정확히 하나의 가능한 답변이 있으며, 그 반대의 경우도 마찬가지다.

그 독특한 게임들;0{\displaystyle \varepsilon ,\delta>0}지속적인 K{K\displaystyle}은 김치는에 대한 상수의 모든 충분히 작은 쌍,δ 을 ε 추측은 NP에 모든 문제 크기 K{K\displaystyle}의 완전성 1− δ을 가진 알파벳에 대한 probabilistically 억제할 수 있는. 증거 가지고 있는 그런 상황. {\dis$플레이스타일 1-\delta },$ $건전성{\displaystyle }$$$soundness ${\displaystyle \varepsilon },$ 랜덤성$$복잡성 $($ ${\displaystyle n}$){\$displaystyle O(\log n)},$ 독특한 게임이다$$.

관련성

P ≠ NP 대 UGC를 가정하는 근사성 결과

문제	폴리 시간 근사	NP 경도	UG 경도
최대 2SAT	${\displaystyle 0.940\property }$[5]	$#\displaystyle 0.954\disp +\barepsilon }$[6]	${\displaystyle 0.9439\190 +\barepsilon }$[7]
맥스 컷	$0.878...\cHB }$[8]	${\displaystyle {\tfrac {16}{17}+\barepsilon \ 약 0.941}$[6]	${\displaystyle 0.878\limit +\bar렙실론}$[7]
최소 꼭지점 커버	${\displaystyle 2}$	$1.360\170 -\bar렙실론 }$[9]	$2-\varepsilon }$[10]
피드백 호 세트	${\displaystyle O(\log n\log \log n)}$[11]	$1.360\170 -\bar렙실론 }$[9]	모든 상수[12]
최대 Acyclic 하위 그래프	${\displaystyle {\tfrac {1}{1}:{2}}+\Oomega(1/{\sqrt{\Delta }})}$[13]	${\displaystyle {\tfrac {65}{66}}}$[14]	${\displaystyle {\tfrac {1}{1}:{2}}+\varepsilon }$[12]
중간	${\displaystyle {\tfrac {1}{3}}$	${\displaystyle {\tfrac {47}{48}}}$[15]	${\displaystyle {\tfrac {1}{3}+\varepsilon }$[16]

투표와 거품 같은 것들에 대한 아주 자연스럽고 본질적으로 흥미로운 진술들이 UGC를 공부하면서 막 튀어나왔다.비록 UGC가 거짓으로 판명되더라도, 그것은 많은 흥미로운 수학 연구에 영감을 주었다.

— Ryan O’Donnell, ^[1]

이 독특한 게임 추측은 근사치 경도 이론의 특정 질문에 대한 진전을 이루기 위해 Subhash Khot에 의해 2002년에 도입되었다.

고유한 게임 추측의 진실은 알려진 많은 근사 알고리즘의 최적성을 암시할 것이다(P ≠ NP를 가정한다).예를 들어, Geemans와 Williamson의 알고리즘이 그래프의 최대 컷에 근사치를 적용하여 달성한 근사비는 고유 게임 추측과 P n NP를 가정할 때 어떤 첨가 상수 내에서든 최적이다.

고유한 게임 추측이 암시하는 것으로 알려진 결과의 목록은 보다 약한 가정 P ≠ NP에 상응하는 최상의 결과와 함께 인접 표에 표시된다. $c{\displaystyle }$ +${\displaystyle \epsilon }$ ${\displaystyle c+\varepsilon }$ 또는$$ c -${\displaystyle \epsilon }$ ${\displaysty c-\varepsilon }$의 상수는 결과가 모든 상수에 대해 유지됨을 의미한다$$.문제 크기$)$ 각각 $c{\displaystyle }$ ${\displaystyle c}$보다 크거나 작음.

토론 및 대안

현재 독특한 게임 추측의 진실에 대해서는 공감대가 형성되지 않고 있다.그 추측의 어떤 더 강력한 형태는 반증되었다.

다른 형태의 추측에 따르면, 고유 게임의 값이 적어도 $1{\displaystyle \mathrm{}}$- ${\displaystyle \Delta }${\$displaystyle 1-\delta$}일$$ 때, 값이 $최대{\displaystyle }$ ${\displaystyle \varepsilon }$일 때, 다항식 시간 알고리즘에는 (NP-hard는 아닐지 몰라도) 구별할 수 없다$$.이러한 형태의 추측은 근사치 경도의 적용에 여전히 유용할 것이다.

위의 추측 공식에서 상수 > 0 ${\displaystyle \delta >0}$은 P = NP가 아닌 한 필요하다. 고유성 요건이 제거된 경우 $\Delta {\displaystyle }$ ${\displaystyle =}$ ${\displaystyle 0}${\$displaystyle \delta =0}$인 경우에도 평행 반복 정리에서는 해당 문장이 참인 것으로 알려져 있다$.$

마레크 카르핀스키와 워렌 슈디는^[17] 독특한 게임 문제의 밀도 높은 사례를 위한 선형 시간 근사 체계를 구축했다.

2008년에 Prasad Raghavendra는 만약 독특한 게임 추측이 사실이라면, 모든 제약조건 만족 문제에 대해 가장 좋은 근사율은 특정한 단순한 세미데마인 프로그래밍 인스턴스(특히 다항식)에 의해 제공된다는 것을 보여주었다.^[18]

2010년 프라사드 라그하벤드라(Prasad Raghavendra)와 데이비드 슈레르는 "갭-스몰셋 확장" 문제를 정의했고, NP-하드라고 추측했다.이 추측은 독특한 게임 추측을 내포하고 있다.^[19]또한 완전한 초당적 서브그래프를 찾기 위한 근사치 결과의 강한 경도를 입증하기 위해 사용되었다.^[20]

2010년, 산제프 아로라, 보아즈 바락, 데이비드 슈레르는 독특한 게임 문제에 대한 하위존재 시간 근사 알고리즘을 발견했다.^[21]

2012년에는 값이 최대 ${\displaystyle \frac{3}{}}$ $8{\displaystyle \frac{\mathrm{}}{}}$ +${\displaystyle \Delta }$ ${\displaystyle {\tfrac {3}{8}}+\delta }$인 인스턴스와 값이$$ $최소{\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle \frac{1}{}}$ 2 ${\$ {$1}{2}}$인 인스턴스를 구분하는 것이$$ NP-hard인 것으로 나타났다.^[22]

2018년에는 연이은 논문 끝에 2-2게임 추측이라 불리는 추측의 약한 버전이 입증됐다.어떤 의미에서 이것은 원래의 추측[1][2]의 "반"을 증명한다.이것은 또한 고유 라벨 표지에 대해 가장 잘 알려진 간격을 개선한다$.$^[23] 최대 $\Delta {\displaystyle }$ ${\displaystyle \delta }$의 값을 가진 인스턴스와 값이$$ $최소{\displaystyle \frac{\mathrm{}}{}}$ 1 ${\displaystyle \frac{2}{}}$ ${\${\$tfrac${1$}{1}{$2}}인 인스턴스를 구분하는 것은 NP 하드다.

메모들

참조

• Khot, Subhash (2010), "On the Unique Games Conjecture", Proc. 25th IEEE Conference on Computational Complexity (PDF), pp. 99–121, doi:10.1109/CCC.2010.19.