This is a good article. Click here for more information.

클라이크 문제

Clique problem
Brute force 알고리즘은 모든 C(7,4) = 35개의 4-Vertex 하위 그래프를 체계적으로 점검하여 이 7-Vertex 그래프(7-Vertex 경로 그래프의 보완)에서 4-클릭을 찾아낸다.

컴퓨터 과학에서, clique 문제는 그래프에서 clique(정점들의 하위 집합들, 모두 서로 인접한, 완전한 하위 그래프라고도 함)를 찾는 계산상의 문제다.그것은 어떤 패거리, 그리고 패거리에 대한 어떤 정보를 찾아야 하는지에 따라 몇 가지 다른 공식들을 가지고 있다.clique 문제의 일반적인 공식화에는 최대 clique(정점 수가 가장 많은 clique), 가중 그래프에서 최대 중량 clique 찾기, 모든 최대 clique(확대할 수 없는 clique) 나열, 그래프에 주어진 siz보다 큰 clique가 포함되어 있는지 시험하는 의사결정 문제 해결 등이 포함된다.e

패거리 문제는 다음의 현실 환경에서 발생한다.그래프의 꼭지점이 사람을 나타내고, 그래프의 가장자리가 상호 친분을 나타내는 소셜 네트워크를 생각해 보자.그러면 패거리란 모두 서로를 알고 있는 사람들의 하위 집합을 나타내며, 패거리 찾기의 알고리즘은 이러한 상호 친구 집단을 발견하는데 사용될 수 있다.사회관계망에서의 그것의 응용과 함께, clique 문제는 또한 생물정보학, 계산화학에도 많은 응용을 가지고 있다.

대부분의 파벌문제는 어렵다.패거리 결정 문제는 NP-완전(Karp의 21개 NP-완전성 문제 중 하나)이다.최대 집단을 찾는 문제는 난해한 고정변수일 뿐 아니라 근사하기도 어렵다.그리고 모든 최대 계층을 나열하는 것은 기하급수적으로 많은 최대 계층이 있는 그래프가 존재하기 때문에 기하급수적인 시간이 필요할 수 있다.따라서 클라이크 문제에 관한 이론의 상당 부분은 보다 효율적인 알고리즘을 인정하는 특수한 유형의 그래프를 식별하거나, 다양한 연산 모델에서 일반적인 문제의 연산 난이도를 설정하는 데 전념하고 있다.

최대 집단을 찾기 위해 모든 하위 집합을 체계적으로 검사할 수 있지만, 이러한 종류의 무차별적인 강제 검색은 수십 개의 정점 이상을 구성하는 네트워크에 실용적이기에는 너무 많은 시간이 걸린다.이 문제에 대해 알려진 다항식 시간 알고리즘은 없지만, 브루트 포스 검색보다 더 효율적인 알고리즘은 알려져 있다.예를 들어, Bron-Kerbosch 알고리즘을 사용하여 최악의 경우 최적 시간으로 모든 최대 패밀리를 나열할 수 있으며, 패당 다항 시간(polyomial time)으로 나열할 수도 있다.

기록 및 응용 프로그램

수학에서 완전한 하위 그래프에 대한 연구는 "clike" 용어보다 앞서 있다.예를 들어, 완전한 서브그래프는 Erdős & Szekeres (1935년)에 의한 램지 이론의 그래프-이론적 개혁에서 수학 문헌에 일찍 나타난다.그러나 "clike"라는 용어와 알고리즘적으로 분류된 분류의 문제는 모두 사회과학에서 비롯되었다. 사회과학에서는 완전한 하위그래프가 서로 아는 집단인 사회분열을 모형화하는 데 사용된다.루스 앤 페리(1949)는 그래프를 사용하여 소셜 네트워크를 모델링했고, 사회과학 용어를 그래프 이론에 적용했다.그들은 완전한 서브그래프를 "clikes"라고 부른 첫 번째 사람이었다.패거리 문제를 해결하기 위한 첫 번째 알고리즘은 사회학적 응용에 의해 동기 부여가 된 하라리 & 로스(1957)의 알고리즘이다.[1]사회과학 연구자들은 또한 소셜 네트워크의 다양한 다른 종류의 집단과 최대 규모의 집단, 네트워크 내의 사람 또는 행위자 모두가 여러 가지 다른 종류의 연결 관계 중 하나를 공유하는 "동화 부분군"을 정의했다.또한 이러한 일반적인 집단 개념의 상당수는 가장자리가 소셜 네트워크로부터 관련 행위자 쌍을 나타내는 비방향 그래프를 구성한 다음 집단 문제에 대한 알고리즘을 이 그래프에 적용함으로써 찾을 수 있다.[2]

하라리와 로스의 작품 이후, 다른 많은 사람들은 다양한 버전의 패거리 문제에 대한 알고리즘을 고안해냈다.[1]1970년대에, 연구원들은 최악의 경우 분석의 관점에서 이 알고리즘들을 연구하기 시작했다.예를 들어, Tarjan & Troyowski(1977년)는 최대 클라이크 문제의 최악의 복잡성에 대한 초기 작품이다.또한 1970년대에 쿡(1971년)과 카프(1972년)의 연구를 시작으로, 연구자들은 NP-완전성 이론과 관련 난해성 결과를 이용하여 패거리 문제의 인식 난이도에 대한 수학적 설명을 제공하기 시작했다.1990년대에 파이지 외 연구진(1991)을 시작으로 뉴욕 타임즈에 보도된 획기적인 일련의 논문들은 (P n NP를 가정하면) 문제의 정확하고 효율적으로 근사조차 할 수 없다는 것을 보여주었다.[3]

화학에는 표적 구조와[4] 일치하는 화학 물질을 찾고 분자 도킹과 화학 반응의 결합 부위를 모델링하기 위해 집단 탐색 알고리즘이 사용되어 왔다.[5]그것들은 또한 다른 분자들 안에서 비슷한 구조를 발견하는데 사용될 수 있다.[6]이러한 응용 프로그램에서는 각 꼭지점이 일치하는 원자 쌍을 나타내는 그래프를 형성하는데, 두 개의 분자 각각에서 한 개씩이다.두 꼭지점은 그들이 나타내는 일치점이 서로 호환되는 경우 가장자리로 연결된다.예를 들어, 양립가능하다는 것은 두 분자 내의 원자 사이의 거리가 주어진 공차 내에서 대략 같다는 것을 의미할 수 있다.이 그래프의 클라이크는 모든 일치된 원자가 서로 호환되는 일치된 쌍의 원자를 나타낸다.[7]이 방법의 특별한 경우는 두 그래프의 최대 공통 유도 하위 그래프를 찾는 문제를 제품에서 최대 집단을 찾는 문제로 줄이기 위해 그래프의 모듈형 제품을 사용하는 것이다.[8]

자동 테스트 패턴 생성에서, 패치를 찾으면 테스트 세트의 크기를 바인딩하는 데 도움이 될 수 있다.[9]생물정보학에서는 진화의 나무를 유추하고 [10]단백질 구조를 예측하며 [11]밀접하게 상호작용하는 단백질 군집을 찾기 위해 집단탐색 알고리즘이 사용되어 왔다.[12]종속성 그래프에 분류 목록을 나열하는 것은 특정 랜덤 프로세스를 분석하는 데 있어 중요한 단계다.[13]수학에서 하이퍼큐브 대면 타일링에 대한 켈러의 추측은 관련 그래프에 클라이크 찾기 알고리즘을 사용해 백범례를 찾아낸 라가리아스&쇼어(1992)에 의해 반증됐다.[14]

정의들

주요 기사: 클라이크 (그래프 이론)
표시된 그래프에는 최대 클라이크 1개, 삼각형 {1,2,5} 및 최대 클라이크 4개, 쌍 {2,3}, {3,4}, {4,5}, {4,6}이(가) 더 있다.

비방향 그래프는 한정된 정점 집합과 순서가 정점 쌍들의 집합에 의해 형성되는데, 이를 에지라고 한다.관례에 따라 알고리즘 분석에서 그래프의 정점 수는 n으로 표시되고 가장자리 수는 m으로 표시된다.그래프 G의 클라이크는 G의 완전한 서브그래프다.즉, K의 모든 두 꼭지점이 G의 가장자리의 두 끝점이라는 정점의 부분 집합 K이다. 최대 클릭은 더 이상 정점을 추가할 수 없는 클릭이다.최대 클라이크의 일부가 아닌 각 꼭지점 v에 대해, v가 클라이크에 추가되지 않도록 v에 인접하지 않고 클라이크에 있는 또 다른 꼭지점 v는 클라이크에 v가 추가되는 것을 방지한다.최대 클라이크는 가능한 최대 정점 수를 포함하는 클라이크다.클릭 수 Ω(G)은 G의 최대 클릭에서 정점의 수입니다.[1]

몇몇 밀접하게 관련된 집단 발견 문제가 연구되었다.[15]

  • 최대 클라이크 문제에서 입력은 비방향 그래프, 출력은 그래프에서 최대 클라이크다.최대 집단이 여러 개일 경우 그 중 하나를 임의로 선택할 수 있다.[15]
  • 가중치 있는 최대 클릭 문제에서 입력은 정점(또는 빈도가 낮은 에지)에 가중치가 있는 비방향 그래프이며 출력은 최대 총 중량을 가진 클릭이다.최대 클라이크 문제는 모든 체중이 동일한 특수한 경우다.[16]가중치의 합을 최적화하는 문제뿐만 아니라, 다른 더 복잡한 이크리테리온 최적화 문제도 연구되었다.[17]
  • 최대 클릭 목록 문제에서 입력은 간접되지 않은 그래프이며, 출력은 모든 최대 클릭의 목록이다.최대 클라이크 문제는 최대 클라이크가 모든 최대 클라이크 중에서 포함되어야 하기 때문에 최대 클라이크 리스트 문제에 대한 알고리즘을 서브루틴으로 사용하여 해결할 수 있다.[18]
  • k-clik 문제에서 입력은 비방향 그래프와 숫자 k이다.출력은 k 정점이 있는 경우 k 정점이 있는 클라이크 또는 달리 k-클라이크가 없음을 나타내는 특수 값이다.이 문제의 일부 변형에서 출력은 k 크기의 모든 부류를 나열해야 한다.[19]
  • clique 결정 문제에서 입력은 비방향 그래프와 숫자 k이며, 출력은 부울 값: 그래프에 k-clique가 포함되어 있으면 true, 그렇지 않으면 false이다.[20]

이 문제들 중 첫 번째 네 가지는 모두 실제 적용에서 중요하다.패거리 결정 문제는 실용적으로 중요하지 않다; 그것은 패거리 발견 문제에 NP-완전성 이론을 적용하기 위해 이러한 방식으로 공식화된다.[20]

clique 문제와 독립적 set 문제는 상호보완적이다: G의 clique는 G의 보완 그래프에서 독립된 집합이며, 그 반대도 마찬가지다.[21]따라서 많은 계산 결과가 어느 문제에나 똑같이 잘 적용될 수 있으며, 일부 연구 논문은 두 문제를 명확하게 구분하지 않는다.그러나 두 문제는 제한된 그래프 패밀리에 적용할 때 서로 다른 속성을 갖는다.예를 들어, 독립 집합 문제는 평면 그래프에서 NP-hard로 유지되는 동안 평면 그래프의[22] 경우 다항식 시간에 해결할 수 있다.[23]

알고리즘

단일 최대 클라이크 찾기

최대 집단은 때로는 포함-최대 집단으로 불리며, 더 큰 집단에 포함되지 않는 집단이기도 하다.그러므로 모든 패거리들은 최대 패거리 속에 담겨 있다.[24]최대 집단은 매우 작을 수 있다.그래프는 정점이 많은 최대값이 아닌 클릭과 최대값인 2의 별도 클릭을 포함할 수 있다.최대(즉, 가장 큰) 집단은 반드시 최대치지만, 그 반대는 유지되지 않는다.모든 최대 클라이크가 최대인 그래프 종류가 있다; 이것들은 잘 가려진 그래프의 보완물로서, 모든 최대 독립 집합이 최대인 그래프들이다.[25]그러나 다른 그래프에는 최대값이 아닌 최대 구분이 있다.

단 하나의 최대 패거리도 직설적인 탐욕 알고리즘으로 찾을 수 있다.임의의 클라이크(예: 단일 꼭지점 또는 빈 집합)로 시작하여 그래프의 나머지 정점을 루핑하여 한 번에 한 꼭지점씩 현재 클라이크를 성장시킨다.이 루프가 검사하는 각 꼭지점 v에 대해 이미 클릭에 있는 모든 꼭지점에 인접한 경우 클릭에 v를 추가하고 그렇지 않으면 v를 폐기하십시오.이 알고리즘은 선형 시간으로 실행된다.[26]최대 집단을 쉽게 찾을 수 있고, 그 잠재적인 작은 크기 때문에, 최대 집단을 찾거나 그 외의 큰 집단을 찾는 훨씬 더 어려운 알고리즘 문제에 더 많은 관심을 기울였다.그러나 병렬 알고리즘에 대한 일부 연구는 최대 정벌을 찾는 문제를 연구했다.특히 다항식 시간 함수의 등급에 대해서는 사전 편찬적으로 첫 번째 최대 클라이크(위의 알고리즘에 의해 발견된 클라이크)를 찾는 문제가 완결된 것으로 나타났다.이 결과는 병렬 복잡도 등급 NC 내에서 문제를 해결할 가능성이 낮다는 것을 의미한다.[27]

고정크리크

그래프 G에 k-Vertex clique가 포함되어 있는지 여부를 테스트할 수 있으며, 그 안에 들어 있는 그러한 clique를 짐승의 힘 알고리즘을 사용하여 찾을 수 있다.이 알고리즘은 k 정점을 가진 각 서브그래프를 검사하고 그것이 집단을 형성하는지 여부를 확인한다.큰 O 표기법을 사용하여 표현된 것처럼 Ok(n2 k) 시간이 걸린다.이는 확인할 O(nk) 하위 그래프가 있으며, 각 하위 그래프는 G에 존재 여부를 확인해야 하는 O(k2) 가장자리가 있기 때문이다.따라서 k가 고정 상수일 때마다 다항식 시간에 문제를 해결할 수 있다.그러나 k가 고정된 값을 가지지 않고 대신 문제에 대한 입력의 일부에 따라 달라질 수 있는 경우 시간은 기하급수적이다.[28]

집단 발견 문제의 가장 간단한 경우는 그래프에서 삼각형을 찾거나, 그래프가 삼각형이 없는지를 동등하게 결정하는 것이다.가장자리가 m인 그래프 G에는 최대 θ(m3/2) 삼각망이 있을 수 있다(이 바인딩이 빠듯함을 나타내기 위해 큰 세타 표기법을 사용).이 공식의 최악의 경우는 G 자체가 패거리일 때 발생한다.따라서 모든 삼각형을 나열하는 알고리즘은 최악의 경우(큰 오메가 표기법 사용) 최소 Ω(m3/2)의 시간이 소요되어야 하며, 이 시간 바운드와 일치하는 알고리즘이 알려져 있다.[29]예를 들어, 지바 & 니시제키(1985)는 정점을 가장 높은 도에서 가장 낮은 도 순서로 정렬하고, 그 다음 정렬된 목록의 각 정점 v를 통해 반복하여 목록에 v를 포함하며 이전의 정점을 포함하지 않는 삼각형을 찾는 알고리즘을 설명한다.이렇게 하려면 알고리즘이 v의 모든 인접 항목을 표시하고, 끝점이 두 개 표시된 모든 Edge에 대해 삼각형을 출력하는 v의 인접 항목을 검색한 다음 그래프에서 표시를 제거하고 v를 삭제하십시오.저자들이 보여주듯이, 이 알고리즘의 시간은 그래프(a(G)로 표시된)의 수목성에 가장자리 수를 곱한 O(m a(G)로 비례한다.수목성은 최대 O(m1/2)이기 때문에 이 알고리즘은 시간 O(m3/2)로 실행된다.보다 일반적으로 모든 k-Vertex cliques는 전력에 대한 수목성을 곱한 가장자리 수에 비례하는 시간이 걸리는 유사한 알고리즘(k - 2)으로 나열할 수 있다.평면 그래프(또는 비교 부분 닫힘 그래프 패밀리의 일반 그래프)와 같은 지속적인 수목성의 그래프의 경우, 이 알고리즘은 입력 크기에서 선형이기 때문에 O([19]m) 시간이 걸린다.

단 하나의 삼각형만을 원하거나 그래프가 삼각형이 없다는 확신이 있다면 더 빠른 알고리즘이 가능하다.Itai & Rodeh(1978)가 관찰한 바와 같이, 인접한 행렬과 인접 행렬의 제곱이 동일한 셀에 0이 아닌 항목을 포함하는 경우에만 그래프가 삼각형을 포함한다.따라서 빠른 행렬 곱셈 기법을 적용하여 시간 O(n2.376)에서 삼각형을 찾을 수 있다.Alon, Yuster & Zwick(1994)은 빠른 행렬 곱셈을 사용하여 O(m3/21.41)까지의 삼각형 찾기를 위한 O(m) 알고리즘을 개선했다.빠른 매트릭스 곱셈에 기초한 이러한 알고리즘은 k의 더 큰 값에 대한 k-clike를 찾는 문제로도 확장되었다.[30]

모든 최대 계층 나열

Moon & Moser(1965년)의 결과로, 모든 n-vertex 그래프는 최대n/3 3개의 최대 분열을 가진다.그것들은 Bron & Kerbosch(1973)의 재귀적 역추적 절차인 Bron-Kerbosch 알고리즘에 의해 나열될 수 있다.이 절차의 주요 재귀적 서브루틴에는 세 가지 주장이 있다: 부분적으로 구성된 (최대치가 아닌) 패거리, 패거리에 추가될 수 있는 후보 정점 집합, 그리고 추가되어서는 안 되는 또 다른 정점 집합. (그렇게 하는 것은 이미 발견된 패거리로 이어질 것이기 때문이다.)알고리즘은 후보 정점을 하나씩 부분 클라이크에 추가해 각각의 정점을 재귀적으로 호출한다.이 정점들을 각각 시도한 후에, 그것은 그것을 다시 추가되어서는 안 되는 정점들의 집합으로 이동시킨다.이 알고리즘의 변형은 최악의 경우 실행 시간 O(3n/3)로 표시되며, 나열해야 할 클릭 수와 일치한다.[31]따라서 이는 모든 최대 패거리의 나열 문제에 대해 최악의 경우 최적의 해결책을 제공한다.또한, 브론-케르보쉬 알고리즘은 대안보다 실제 실행 속도가 더 빠르다고 널리 보고되어 왔다.[32]

그러나 최악의 경우보다 패거리 수가 현저히 적을 경우 다른 알고리즘이 선호될 수 있다.츠키야마 외 연구진(1977)이 보여주었듯이, 모든 최대 집단을 생성된 집단당 다항식인 시간 내에 그래프에 나열하는 것도 가능하다.실행 시간이 출력 크기에 따라 달라지는 알고리즘과 같은 알고리즘을 출력 민감 알고리즘이라고 한다.이들의 알고리즘은 G에서 임의의 정점 v를 제거하여 형성된 그래프 G \ v의 최대 정점과 주어진 그래프 G의 최대 정점과 관련된 다음 두 가지 관측치에 기초한다.

  • G \ v의 모든 최대 클릭 K에 대해, K는 G에서 최대 클릭을 계속 형성하거나, K ⋃ {v}은(는) G에서 최대 클릭을 형성한다.따라서 G는 적어도 G \ v만큼의 최대 집단을 가지고 있다.
  • v를 포함하지 않는 G의 각 최대 클릭은 G \ v의 최대 클릭이며, v를 포함하지 않는 G의 각 최대 클릭은 v를 추가하고 K에서 v의 non-neighbors를 제거함으로써 G \ v의 최대 클릭 K로부터 형성될 수 있다.

이러한 관찰을 사용하면 그들은 임의로 정점 v를 선택한 다음 G \ v의 각 최대 클릭에 대해 K와 K에 v를 추가하고 v의 비인접 클릭을 제거하여 형성된 클릭을 모두 출력하는 재귀 알고리즘에 의해 G의 모든 최대 클릭을 생성할 수 있다. 그러나, G의 일부 클릭은 둘 이상의 상위 클럭에서 이러한 방식으로 생성될 수 있다.G \ v의 ique는 G \ v의 상위 항목이 가능한 모든 상위 계층 중에서 사전 통계학적으로 최대인 경우에만 G에서 클릭을 출력하여 중복 항목을 제거한다.이 원리에 기초하여, 그들은 G의 모든 최대 균열이 클라이크당 시간 O(mn)에 생성될 수 있음을 보여준다. 여기서 m은 G의 가장자리 수, n은 정점 수이다.치바&니시세키(1985)는 이를 일족당 O(ma)로 개선하는데, 여기서 a는 주어진 그래프의 수목성이다.Makino & Uno(2004)는 빠른 매트릭스 곱셈을 기반으로 한 대체 출력 민감 알고리즘을 제공한다.존슨 앤 얀나카키스(1988)는 모든 최대 집단을 사전순으로 나열할 수 있으며, 집단당 다항식 지연도 가능하다는 것을 보여준다.그러나 이 알고리즘의 효율을 위해서는 순서 선택이 중요하다: 이 순서의 역순에 대해서는 P = NP가 아닌 한 다항식 지연 알고리즘이 없다.

이 결과에 기초하여, 모든 최대 패밀리를 다항 시간 내에 나열할 수 있으며, 패밀리의 수가 다항식 경계인 그래프 패밀리의 경우 가능하다.이러한 패밀리는 화음 그래프, 완전한 그래프, 삼각형이 없는 그래프, 구간 그래프, 경계 상자성 그래프, 평면 그래프를 포함한다.[33]특히 평면 그래프는 선형 시간으로 나열할 수 있는 최대 일정 크기의 O(n) 구분을 가지고 있다.희박하고(최대 정점 수의 일정한 배수의 에지가 있음) 하위 그래프를 찍는 작업으로 닫히는 그래프 제품군도 마찬가지다.[19][34]

임의 그래프에서 최대 분류 찾기

위에 설명한 알고리즘 중 하나를 사용하여 그래프에 모든 최대 클릭을 나열하고 가장 큰 클릭을 반환함으로써 임의의 n-vertex 그래프의 최대 클릭 또는 클릭 수를 O(3n/3) = O(1.4422n) 시간 내에 찾을 수 있다.그러나 이러한 변종파 문제의 경우 최악의 경우 시간제한이 가능하다.타르잔과 트로이우스키(1977)의 알고리즘은 O(2n/3) = O(1.25999n) 시간 내에 이 문제를 해결한다.Bron-Kerbosch 알고리즘과 유사한 재귀적 역추적 방식이지만, 통화 내에서 발견된 집단이 차선적일 것이라는 것을 보여줄 수 있을 때 일부 재귀적 호출을 제거할 수 있다.지안(1986)은 O(20.304n) = O(1.23466n)로, 롭슨(1986)은 더 많은 공간 사용을 희생하면서 O(20.276n) = O(1.2108n)시로 시간을 단축했다.롭슨의 알고리즘은 유사한 역추적 방식(더 복잡한 사례 분석과 함께)과 보완 그래프의 모든 작은 연결 서브그래프에 대해 최적의 솔루션을 미리 계산하는 동적 프로그래밍 기법을 결합한다.이러한 부분적인 해결책은 역추적 재귀의 단축을 위해 사용된다.오늘날 알려진 가장 빠른 알고리즘은 시간 O(2) = O(1.18880.249nn)로 실행되는 롭슨(2001)에 의한 이 방법의 정제된 버전이다.[35]

또한 분기 및 바인딩,[36] 로컬 검색,[37] 탐욕 알고리즘,[38] 제약 프로그래밍 등의 방법에 근거하여 최악의 런타임 보장 없이 최대의 클라이크 문제를 해결하기 위한 경험적 알고리즘에 대한 광범위한 연구가 있었다.[39]부류 발굴을 위해 제안된 비표준 컴퓨팅 방법론에는 DNA 컴퓨팅과[40] 부류 양자 계산이 포함된다.[41]최대 클라이크 문제는 1992-1993년 DIMACS가 후원한 구현 도전과제의 벤치마크로 사용된 그래프 모음의 주제였으며,[42] 이는 공개적으로 이용 가능하다.[43]

그래프의 특수 클래스

이 순열 그래프에서 최대 분류는 정의 순열의 가장 긴 감소 반복(4,3,1)과 (4,3,2)에 해당한다.

평면 그래프와 기타 희소성 그래프 패밀리는 위에서 논의한 바 있다. 즉, 선형 시간 내에 나열할 수 있는 경계 크기의 최대 패밀리가 선형적으로 많다.[19]특히 평면 그래프의 경우, 쿠라토프스키의 정리에 의해 어떤 클라이크도 최대 4개의 정점을 가질 수 있다.[22]

완벽한 그래프는 그 집단의 수가 그들의 색수와 같다는 속성에 의해 정의되며, 이 평등은 또한 각각의 유도된 하위 그래프에도 있다는 것이다.완벽한 그래프의 경우 세미더파인파인 프로그래밍에 기반한 알고리즘을 사용하여 다항 시간 내에 최대 클라이크를 찾을 수 있다.[44]그러나 이 방법은 복잡하고 비조합적이며, 완벽한 그래프의 많은 하위 분류에 대해 전문화된 클라이크 탐색 알고리즘이 개발되었다.[45]초당적 그래프의 보완 그래프에서 Kőnig의 정리는 일치에 대한 기법을 이용하여 최대의 클라이크 문제를 해결할 수 있도록 한다.완벽한 그래프의 또 다른 클래스인 순열 그래프에서 최대 클릭은 그래프를 정의하는 순열의 가장 긴 감소 반복이며 가장 긴 감소 반복 문제에 대해 알려진 알고리즘을 사용하여 찾을 수 있다.반대로, 가장 긴 감소 반복문제의 모든 사례는 순열 그래프에서 최대 집단을 찾는 문제로서 동등하게 설명될 수 있다.[46]심지어 Pnueli & Lempel(1972)은 비교가능성 그래프에서 최대 부류에 대한 대안 2차 시간 알고리즘을 제공하는데, 이는 순열 그래프를 특수 사례로 포함하는 광범위한 종류의 완벽한 그래프다.[47]화음 그래프에서, 최대 집단은 제거 순서에 정점을 나열하고, 이 순서에서 각 정점의 정점 주변을 확인함으로써 찾을 수 있다.[48]

경우에 따라 이러한 알고리즘은 완벽하지 않은 다른 그래프 클래스에도 확장될 수 있다.예를 들어 원 그래프에서 각 꼭지점의 근방은 순열 그래프이므로 원 그래프에서 순열 그래프 알고리즘을 각 근방에 적용하면 최대 클릭을 찾을 수 있다.[49]마찬가지로 단위 디스크 그래프(알려진 기하학적 표현 포함)에는 정점 쌍의 공유된 지역에 초당적 그래프의 보완 알고리즘을 적용하는 것에 기초한 최대 클릭에 대한 다항 시간 알고리즘이 있다.[50]

Erdős-Rényi 모델(각 에지가 확률 1/2로 나타나며 다른 에지와는 독립적으로)에서 도출한 랜덤 그래프에서 최대 클라이크를 찾는 알고리즘 문제는 Karp(1976년)에 의해 제안되었다.무작위 그래프의 최대 클라이크는 로그 크기가 높고 확률이 높기 때문에 예상 시간O(log2n) 2에서 짐승의 힘 검색을 통해 찾을 수 있다.이것은 준공칭 시간 제한이다.[51]이러한 그래프의 클릭 수는 대개 2개의2 로그에 매우 가깝지만, 보다 정교한 랜덤화 근사치 기법뿐만 아니라 단순한 탐욕 알고리즘은 절반의 크기 로그가2 있는 클릭만 찾을 수 있다.이러한 그래프에서 최대값의 수는 logn에서2 높은 확률 지수 값을 가지며, 이는 모든 최대값을 나열하는 방법이 다항 시간 내에 실행되지 않도록 방지한다.[52]이 문제의 어려움 때문에, 몇몇 저자들은 큰 패거리들을 추가함으로써 증강된 무작위 그래프에 심어진 패거리 문제, 즉 패거리 문제를 조사해왔다.[53]스펙트럼 방법과[54] 세미데임파인 프로그래밍은[55] 크기 Ω(√n)의 숨겨진 부류를 검출할 수 있지만, 현재 크기 o( littlen) (little-o 표기법을 사용하여 표현)의 부류를 검출하는 다항식 시간 알고리즘은 알려져 있지 않다.[56]

근사 알고리즘

몇몇 저자들은 최대치는 아니지만 다항식 시간에서 찾을 수 있는 최대치에 가까운 크기를 갖는 집단이나 독립된 집합을 찾으려는 근사 알고리즘을 고려했다.이 작업의 많은 부분이 보완적 클라이크 문제에 대해 이치에 맞지 않는 사례인 희소성 그래프에서 독립된 집합에 초점을 맞추었지만, 그러한 첨사성 가정을 사용하지 않는 근사 알고리즘에 대한 연구도 있었다.[57]

Feige(2004)는 상수 k에 대해 클릭 수 Ω(n/lognk)이 있는 그래프에서 크기 Ω(log n/log log n)2의 클릭을 찾는 다항식 시간 알고리즘을 설명한다.더 높은 패거리들이 숫자와 그래프에 둘 다 알고리즘 아무것도 찾고 약속을 지키지two-vertex을 선택은 주어진 입력 그래프의 고질적인 패거리 번호n/log n과 n/log3n, Boppana 및 다른 알고리즘으로 전환 사이에 있다. 이 알고리즘, Halldórsson(1992년)을 사용함으로써, Feige는 도당 지..지 발견한 근사 알고리즘을 제공하ith최대값의 O(n(log log n)/2logn3) 인수 내의 정점 수이 알고리즘의 근사비는 약하지만 현재까지 가장 잘 알려져 있다.[58]아래에서 설명한 근사 경도에 대한 결과는 근사비가 선형보다 유의하게 작은 근사 알고리즘은 존재할 수 없음을 시사한다.

하한

NP-완전성

3-CNF 만족도 인스턴스(x x x y y) ( (~x ~ ~y ~ ~y ~ ~y) reduced (~x y y) reduced (~x y y) reduced.녹색 정점들은 3개의 클라이크를 형성하고 만족스러운 과제에 해당한다.[59]

집단 결정 문제는 NP-완전이다.그것은 1972년 논문 "합병 문제들 사이의 축소 가능성"[60]에서 NP-완전성을 보여준 리차드 카프의 원래 21개 문제들 중 하나였다.이 문제는 NP-완전성 문제 이론을 소개하는 스티븐 쿡의 논문에서도 언급되었다.[61]결정문제의 경도 때문에 최대 집단을 찾는 문제도 NP-hard이다.해결할 수 있다면 결정문제의 입력으로 주어진 크기 매개변수와 최대 집단의 크기를 비교함으로써 결정문제도 해결할 수 있을 것이다.

Karp의 NP 완성도 증명은 Boolean 만족도 문제로부터 많은 1을 줄인 것이다.CNF(Concollective Normal Form)의 부울 공식을 최대 클라이크 문제의 동등한 인스턴스로 변환하는 방법을 기술한다.[62]만족도는 결국 쿡-레빈 정리에서 NP-완전성이 입증되었다.주어진 CNF 공식에서 Karp는 모든 쌍(v,c)에 대해 정점을 갖는 그래프를 형성한다. 여기서 v는 변수 또는 그 부정이고 c는 v를 포함하는 공식의 절이다.이들 정점 중 두 개는 서로 다른 절에 대해 호환 가능한 변수 할당을 나타내는 경우 가장자리에 의해 연결된다.즉, c ≠ d와 u와 v가 서로의 부정이 아닐 때마다 (v,c)에서 (u,d)까지의 에지가 있다.k가 CNF 공식의 절 수를 나타내는 경우, 이 그래프의 k-vertex 분류는 공식을 충족하기 위해 일부 변수에 진실 값을 할당하는 일관된 방법을 나타낸다.따라서 이 공식은 k-Vertex clique가 존재하는 경우에만 만족한다.[60]

일부 NP 완료 문제(평면 그래프에서 여행 판매원 문제 등)는 입력 크기 매개변수 n의 하위 선형 함수에서 기하급수적으로 빠른 시간 내에 해결할 수 있다.[63]그러나, 그러한 하위존재 시간범위는 임의 그래프의 클라이크 문제에 대해 가능할 것 같지 않은데, 이는 다른 많은 표준 NP-완전한 문제에 대해서도 유사하게 하위존재 한계를 의미할 수 있기 때문이다.[64]

회로 복잡성

k = 3 및 n = 4에 대한 n-vertex 그래프에서 k-clike를 검출하기 위한 단조 회로.회로에 대한 각 입력은 그래프에서 특정(빨간색) 에지의 유무를 부호화한다.회로는 하나의 내부 및 게이트를 사용하여 각 잠재적 k-clike를 검출한다.

clique 문제의 계산적 난이도는 회로 복잡성의 몇 가지 하한을 입증하는 데 사용되게 했다.주어진 크기의 집단이 존재한다는 것은 단조로운 그래프 속성인데, 주어진 그래프에 집단이 존재한다면 어떤 수퍼그래프에도 존재할 것이라는 뜻이다.이 속성은 단조롭기 때문에, 주어진 고정된 클라이크 크기에 대한 클라이크 결정 문제를 해결하기 위해 오직 게이트와 게이트만을 사용하는 단조로운 회로가 존재해야 한다.그러나 이들 회로의 크기는 정점 수와 정점 수의 큐브 루트에서 지수화된 클릭 크기의 초폴리노멀 함수로 증명될 수 있다.[65]소수의 NOT 관문이 허용되더라도, 그 복잡성은 초공칭으로 남아 있다.[66]또한 경계 팬인 게이트를 사용하는 클라이크 문제에 대한 모노톤 회로의 깊이는 적어도 클라이크 크기의 다항식이어야 한다.[67]

의사 결정 트리 복잡성

4Vertex 그래프에서 3-clik의 존재를 탐지하는 간단한 결정 트리.최적의 바운드 n(n - 1)/2와 일치하는 "빨간 가장자리가 존재하는가?" 형태의 최대 6문항을 사용한다.

그래프 속성을 결정하는 (결정론적) 의사결정 트리 복잡성은 "정점 u와 정점 v 사이에 에지가 있는가?"라는 형식의 질문 수입니다. 이 질문은 그래프에 특정 속성이 있는지 여부를 결정하기 위해 최악의 경우 답변해야 한다.즉, 문제에 대한 부울 결정 트리의 최소 높이인 것이다.n(n - 1)/2의 가능한 질문이 있다.따라서 그래프 속성은 최대 n(n - 1)/2 문항으로 결정할 수 있다.또한 주어진 그래프의 속성이 있는지 여부를 정확하게 판단하기 위해 무작위화 또는 양자 알고리즘이 답해야 하는 예상 질문 수(최악의 경우 입력)인 속성의 무작위 및 양자 결정 트리 복잡성을 정의할 수 있다.[68]

clique를 포함하는 속성은 모노톤이기 때문에, 비삼각적 모노톤 그래프 속성을 결정하는 결정론적 의사결정 트리 복잡성은 정확히 n(n - 1)/2라고 하는 Aandera-Karp-Rosenberg 추측에 의해 다루어진다.임의의 단일 그래프 속성의 경우, 이러한 추측이 입증되지 않은 상태로 남아 있다.단, 결정론적 의사결정 나무와 2 and k ≤ n 범위의 k에 대해, k-clik를 포함하는 속성은 정확히 볼로바(1976년)에 의해 결정 나무 복잡성이 n(n - 1) (1/2)인 것으로 나타났다.결정론적 의사결정 트리에는 또한 패밀리를 탐지하기 위한 지수적 크기 또는 경계된 크기의 패밀리를 탐지하기 위한 큰 다항식 크기가 필요하다.[69]

또한 Aanderaa-Karp-Rosenberg 추측에 따르면 비경쟁적 단조함수의 무작위화된 의사결정 트리 복잡성은 θ(n2)이다.그 추측은 다시 입증되지 않은 채 남아 있지만, 2 ≤ ≤ n에 대한 kik clic을 포함하는 성질 때문에 해결되었다.이 속성은 무작위화된 의사결정 나무의 복잡성 ((n2)을 갖는 것으로 알려져 있다.[70]양자 결정 트리의 경우 가장 잘 알려진 하한은 Ω(n)이지만 k ≥ 3의 경우 일치하는 알고리즘은 알려져 있지 않다.[71]

고정-모수 난해석

매개변수화된 복잡성은 자연적으로 작은 정수 매개변수 k가 장착되어 있고 그래프에서 k-clik를 찾는 등 k가 증가할수록 문제가 더 어려워지는 문제에 대한 복잡성-이론적 연구다.문제는 크기 n의 입력에 대해 이를 해결하기 위한 알고리즘과 함수 f가 있으면 고정 매개변수가 추적 가능하다고 하는데, 이 알고리즘은 시간 f(k) n으로O(1) 실행된다.즉, k의 어떤 고정 값에 대해 다항 시간 내에 해결할 수 있는 경우, 더 나아가 다항식의 지수가 k에 의존하지 않는 경우 고정 매개변수를 추적할 수 있다.[72]

k-vertex clique를 찾기 위해, brute force 검색 알고리즘에는 실행 시간 O(nkk2)가 있다.n의 지수가 k에 의존하기 때문에 이 알고리즘은 고정 매개변수를 추적할 수 없다.빠른 매트릭스 곱셈에 의해 개선될 수 있지만, 실행 시간은 여전히 k에서 선형인 지수를 가지고 있다. 따라서, 비록 clique 문제에 대해 알려진 알고리즘의 실행 시간은 고정 k에 대해 다항식이지만, 이러한 알고리즘은 고정 매개변수 추적성에는 충분하지 않다.다우니 앤 펠로우즈(1995)는 그들이 추측한 고정 매개변수 추적 가능한 알고리즘이 없는 파라메타화된 문제의 계층인 W 계층을 정의했다.그들은 독립된 집합(또는 동등하게, 클라이크)이 이 계층의 첫 번째 단계인 W[1]에게 어렵다는 것을 증명했다.따라서, 그들의 추측에 따르면, clique는 고정 매개변수 추적 가능한 알고리즘을 가지고 있지 않다.더욱이, 이 결과는 많은 다른 문제들의 W[1]-강도의 입증 근거를 제공하며, 따라서 매개변수화된 복잡성에 대한 Cook-Levin 정리의 아날로그적 역할을 한다.[73]

첸 외 (2006)은 지수 시간 가설이 실패하지 않는 한 k-980 clicks를 찾아내는 것은 시간o(k) n으로 할 수 없다는 것을 보여주었다.다시 말하지만, 이것은 고정 매개변수 추적 가능한 알고리즘이 불가능하다는 증거를 제공한다.[74]

최대 집단을 나열하거나 최대 집단을 찾는 문제는 매개변수 k로 고정 매개변수를 추적할 수 없을 것 같지만, 인스턴스 복잡성의 다른 매개변수에 대해서는 고정 매개변수를 추적할 수 있을 수 있다.예를 들어, 두 문제 모두 입력 그래프의 퇴보성에 의해 파라메트릭이 될 때 고정 매개변수가 추적 가능한 것으로 알려져 있다.[34]

근사 경도

3비트 증명 문자열의 2비트 샘플 간의 호환성 관계를 나타내는 그래프.이 그래프의 각 최대 클라이크(삼각형)는 단일 3비트 문자열을 샘플링하는 모든 방법을 나타낸다.clique 문제의 근사성 증명은 더 많은 수의 비트에 대해 유사하게 정의된 그래프의 유도 하위 그래프를 포함한다.

패거리 문제가 근사치 않을 수 있음을 암시하는 약한 결과가 오랫동안 알려져 왔다.개리 앤 존슨(1978)은 클라이크 수가 작은 정수 값을 차지하고 계산하기 어려운 NP이기 때문에 완전한 다항식 시간 근사 체계를 가질 수 없다고 보았다.너무 정확한 근사치를 사용할 수 있는 경우, 그 값을 정수로 반올림하면 정확한 정수가 된다.그러나, 1990년대 초까지만 해도 그 이상은 거의 알려지지 않았는데, 그 때 몇 명의 저자들이 최대 집단의 근사치와 확률적으로 확인할 수 있는 증거 사이에 연관성을 찾기 시작했다.그들은 이러한 연결을 사용하여 최대 집단 문제에 대한 근사치 결과의 경도를 입증했다.[75]이러한 결과에 대한 많은 개선 후에 P = NP가 아닌 한 모든 실제 숫자 > > 0에 대해 O(n1 − ε)보다 나은 요인 내에서 최대 클릭에 근접한 다항 시간 알고리즘은 존재하지 않는다는 것이 현재 알려져 있다.[76]

이러한 유사성 결과에 대한 대략적인 아이디어는 부울 만족도 문제와 같은 NP 완전 문제에 대해 확률적으로 확인할 수 있는 입증 시스템을 나타내는 그래프를 구성하는 것이다.확률적으로 확인할 수 있는 증명 시스템에서 증명서는 일련의 비트들로 표현된다.만족도 문제의 한 예는 그것이 만족스러운 경우에만 유효한 증거를 가지고 있어야 한다.만족도 문제에 대한 입력에 대한 다항식 시간 계산 후, 교정 문자열의 임의로 선택된 소수 위치를 검사하도록 선택하는 알고리즘에 의해 증명 검사를 한다.비트 샘플에서 어떤 값이 발견되느냐에 따라, 체커는 나머지 비트를 보지 않고 증거를 받아들이거나 거부할 것이다.거짓된 부정은 허용되지 않는다. 유효한 증거는 항상 받아들여져야 한다.그러나, 잘못된 증거가 때때로 잘못 받아들여질 수도 있다.모든 유효하지 않은 증거에 대해 검사자가 이를 받아들일 확률은 낮아야 한다.[77]

이러한 유형의 확률적으로 검사 가능한 증명 시스템을 집단 문제로 변환하려면, 증명 검사기의 가능한 각 허용 런에 대해 꼭지점이 있는 그래프를 형성한다.즉, 정점은 검사할 위치 집합의 가능한 무작위 선택 중 하나와 검사자가 증거를 수용하게 하는 위치의 비트 값으로 정의된다.검사된 각 위치에서 0 또는 1의 부분 단어와 나머지 각 위치에서 와일드카드 문자로 나타낼 수 있다.이 그래프에서 두 꼭지점이 인접해 있으며, 해당 두 개의 합격 런이 양쪽이 검사하는 모든 위치에서 동일한 비트 값을 볼 경우.각(유효하거나 유효하지 않은) 증명 문자열은 하나의 패거리에 해당하며, 해당 증명 문자열을 보는 승인 실행 집합과 모든 최대 패거리가 이러한 방식으로 발생한다.이러한 패거리 중 하나는 많은 교정 검사자들이 수용하는 증명 문자열과 일치하는 경우에만 크다.만약 원래의 만족도가 만족스럽다면, 그것은 유효한 증명 문자열, 즉 체커의 모든 실행에 의해 받아들여질 것이고, 이 문자열은 그래프에서 큰 패거리에 해당할 것이다.그러나 원본 인스턴스가 만족스럽지 않으면 모든 증명 문자열은 무효가 되며, 각 증명 문자열은 이를 잘못 수용하는 소수의 검사자 실행만 가지고 있으며, 모든 분류는 작다.따라서, 다항 시간 내에 모든 집단이 작은 큰 분류와 그래프를 가진 그래프와 구별할 수 있거나, 또는 만족도 인스턴스에서 생성된 그래프에 이 근사치를 적용하면 만족스럽지 못한 예와 구별할 수 있을 것이다.아주 좋은 예그러나 P = NP가 아닌 이상 이것은 불가능하다.[77]

메모들

  1. ^ a b c 봄제 외 연구진(1999년), 구틴(2004년).
  2. ^ Wasserman & Faust(1994년).
  3. ^ 코라타(1990).
  4. ^ 로도스 외 (2003).
  5. ^ Kuhl, Capten & Frienden (1983년).
  6. ^ 국립수학문제연구위원회 연산화학(1995)특히 35-36페이지를 보라.
  7. ^ Muegge & Largey(2001년).특히 6-7페이지를 보라.
  8. ^ Barrow & Bustall (1976년).
  9. ^ 함자오글루&파텔(1998년).
  10. ^ 데이앤샌코프(1986)
  11. ^ Samudrala & Moult (1998년).
  12. ^ 스피린 & 미르니(2003년).
  13. ^ 프랭크 스트라우스(1986년).
  14. ^ 라고리아스&쇼르(1992)가 사용한 켈러 그래프는 정점 1048576과 클릭 사이즈 1024를 가지고 있다.그들은 그 패거리들을 위한 합성 구조를 설명했지만, 또한 그들의 검색을 안내하기 위해 작은 그래프에 패거리 찾기 알고리즘을 사용하기도 했다.맥키(2002)는 65536-Vertex Keller 그래프에서 256 사이즈의 패거리를 찾아 증거를 단순화했다.
  15. ^ a b Valente(2002);펠릴로(2009년).
  16. ^ 펠릴로(2009년).
  17. ^ 세투라만&부텐코(2015년).
  18. ^ 발리엔테(2002년).
  19. ^ a b c d 지바&니시세키(1985년).
  20. ^ a b 코멘 외 (2001).
  21. ^ 코멘 외 (2001), 연습 34-1 페이지 1018.
  22. ^ a b 파파디미트리오&얀나카키스(1981년), 지바&니시세키(1985년).
  23. ^ 개리, 존슨 & 스톡마이어(1976년).
  24. ^ 예를 들어 프랭크 스트라우스(1986)를 참조하라.
  25. ^ 배관공(1993년).
  26. ^ 스키에나(2009년), 페이지 526.
  27. ^ 요리(1985년).
  28. ^ 예: 다우니 & 펠로우즈(1995)를 참조한다.
  29. ^ 이타이&로데(1978)는 삼각형이 존재하지만 모든 삼각형을 나열하지 않으면 삼각형을 찾는 O(m3/2) 러닝타임을 알고리즘에 제공하고, 치바&니시세키(1985)는 모든 삼각형을 시간 O(m3/2)로 나열한다.
  30. ^ 아이젠브랜드 & 그랜도니(2004); 클록스, 크래치 & 뮐러(2000);네셰틸 & 폴작(1985); 바실레브스카 & 윌리엄스(2009);유스터(2006년).
  31. ^ 토미타, 다나카 & 다카하시(2006년).
  32. ^ Cazals & Carande(2008);엡스타인, 뢰플러 & 스트래시(2013년).
  33. ^ 로스젠 & 스튜어트(2007)
  34. ^ a b 엡스타인, 뢰플러 & 스트래시(2013년).
  35. ^ 롭슨(2001년).
  36. ^ 발라스 & 유(1986); 카라한 & 파르달로스(1990), 파르달로스 & 로저스(1992), 외스테르그르트(2002);화씨(2002);토미타 & 세키(2003);토미타 & 카메다(2007); 콩크 & 제인비치(2007).
  37. ^ 바티티 & 프로타시(2001); 카타야마, 하마모토 & 나리히사(2005).
  38. ^ 아벨로, 파르달로스 & 레센데(1999년), 그로소, 로카텔리 & 델라 크로체(2004년).
  39. ^ 레긴(2003년).
  40. ^ 오우양 외 연구진(1997)제목이 최대의 파벌을 가리킨다고는 하지만, 본 논문이 해결하는 문제는 사실 최대 파벌 문제다.
  41. ^ 차일드 외 (2002).
  42. ^ 존슨앤트릭(1996년).
  43. ^ DIMACS 챌린지 그래프는 2009-12-17에 액세스한 웨이백 머신에 보관된 2018-03-30의 클라이크 문제에 대한 그래프.
  44. ^ 그뢰첼, 로바스 & 슈리히버(1988)
  45. ^ 골룸빅(1980년).
  46. ^ 골룸빅(1980), 페이지 159.
  47. ^ 심지어, Pnueli & Lempel(1972년).
  48. ^ Blair & Peyton (1993년), Lemma 4.5, 페이지 19.
  49. ^ 가브릴(1973); 골룸빅(1980), 페이지 247.
  50. ^ Clark, Colbourn & Johnson (1990).
  51. ^ 송 (2015년)
  52. ^ 저럼(1992년).
  53. ^ Arora & Barak(2009), 사례 18.2, 페이지 362–363.
  54. ^ 알론, 크리벨레비치 & 수다코프(1998년).
  55. ^ Feige & Krauthgamer(2000년).
  56. ^ 메카, 포틴 앤 위그더슨(2015년).
  57. ^ Boppana & Halldorsson(1992);Feige(2004);할도르손(2000년)
  58. ^ 류 외 (2015년) : "그래프의 정점 수 측면에서 Feige는 현재 가장 잘 알려진 근사비를 보여준다."류 외 연구진은 최대 독립 집합에 대해 쓰고 있지만 근사치 목적상 두 문제 사이에는 차이가 없다.
  59. ^ Sipser로부터 개조(1996)
  60. ^ a b 카프(1972년).
  61. ^ 요리(1971년).
  62. ^ Cook(1971)은 하위 그래프 이형성이 NP-완전하다는 것을 보여주기 위해 기본적으로 만족도 대신 3-SAT에서 동일한 감소를 제공한다.
  63. ^ 립톤과 타르잔(1980).
  64. ^ 임파글리아초, 파투리 & 제인(2001년).
  65. ^ 알론 & 보파나(1987년).클라이크 문제에 대한 모노톤 회로의 초기 및 약한 한계는 발리안트(1983) 및 라즈보로프(1985)를 참조한다.
  66. ^ 아마노&마루오카(2005년).
  67. ^ 골드만&호스태드(1992)는 이 결과를 증명하기 위해 의사소통의 복잡성을 이용했다.
  68. ^ 아로라 & 바라크(2009), 12장 "결정 나무", 페이지 259–269를 참조한다.
  69. ^ 베게너(1988년).
  70. ^ 예를 들어, 이것은 그뢰거(1992년)에서 따온 것이다.
  71. ^ Childs & Eisenberg(2005);Magniez, Santha & Szegedy(2007년).
  72. ^ 다우니 & 펠로우즈(1999년).기술적으로 f는 계산 가능한 함수가 되어야 한다는 추가 요건이 있다.
  73. ^ 다우니 & 펠로우즈(1995년).
  74. ^ 첸 외 (2006).
  75. ^ 코라타(1990);Feige 외 연구진(1991); Arora & Safra(1998); Arora 외 연구진(1998).
  76. ^ Håstad(1999년)는 NP와 ZPP의 불평등이라는 더 강한 복잡성 이론적 가정을 사용하여 이 비율에 대한 근사성을 보여주었다.Khot(2001)은 비교가능성 비율을 더 정밀하게 설명했지만, 훨씬 더 강력한 가정을 가지고 있었다.Zuckerman(2006)은 건설이 P p NP로 가정하는 것을 약화시키는 것을 조롱했다.
  77. ^ a b 이러한 감소는 원래 Feige 외 연구진(1991)에 기인하며, 이후 모든 유사성 증명에 사용된다. 그 증명은 그들이 의존하는 확률적으로 점검 가능한 증명 시스템의 강점과 세부사항에 차이가 있다.

참조

조사 및 교과서

대중언론

연구기사