클릭 문제

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

1. 개요

클리크 문제는 그래프 이론에서 모든 정점 쌍이 서로 연결된 완전 부분 그래프인 클리크를 찾는 문제이다. 극대 클리크, 최대 클리크, 클리크 수와 같은 관련 개념이 있으며, 클리크 문제와 독립 집합 문제는 상호 보완적 관계를 갖는다. 클리크 개념은 1935년 람제이 이론에서 처음 등장했으며, 1949년 사회 연결망 연구에서 "클리크"라는 용어가 사용되었다.

클리크는 사회 연결망 분석, 화학, 생물 정보학 등 다양한 분야에 응용되며, 알고리즘 연구도 활발히 진행되었다. 극대 클리크 찾기, 고정 크기 클리크 찾기, 모든 극대 클리크 나열, 임의 그래프에서 최대 클리크 찾기 등 다양한 알고리즘이 개발되었다. 클리크 결정 문제는 NP-완전 문제로, 회로 복잡도, 의사 결정 트리 복잡도, 고정 매개변수 난해성, 근사 난이도 등 계산 복잡도 측면에서 다양한 연구가 이루어졌다.

더 읽어볼만한 페이지

그래프 이론의 계산 문제 - 외판원 문제
외판원 문제(TSP)는 여러 도시를 모두 한 번씩 방문하고 출발점으로 돌아오는 최소 비용의 이동 순서를 구하는 문제로, NP-난해 문제에 속하며, 배송 계획 등에 응용되고 다양한 해법이 존재한다.
그래프 이론의 계산 문제 - 해밀턴 경로
해밀턴 경로는 그래프의 모든 꼭짓점을 한 번씩 방문하는 경로로, 해밀턴 순환은 이러한 경로가 순환 형태를 띠는 것을 의미하며, 이들은 그래프 이론에서 중요한 개념으로 NP-완전 문제 및 외판원 문제 등에 응용된다.
NP-완전 문제 - 지뢰 찾기
지뢰 찾기는 격자 형태 지뢰밭에서 지뢰를 피해 안전한 칸을 모두 여는 퍼즐 비디오 게임으로, 칸을 열어 지뢰 유무를 확인하며, 윈도우 탑재를 통해 대중화되었고 NP-완전 문제로 분류된다.
NP-완전 문제 - 스도쿠
스도쿠는 9x9 칸에 1부터 9까지의 숫자를 채워 넣는 퍼즐로, 각 가로줄, 세로줄, 3x3 칸에 숫자가 중복 없이 들어가야 하며, 레온하르트 오일러의 라틴 방진을 기반으로 다양한 변형과 응용 연구가 진행되고 있다.

클릭 문제

2. 정의

무방향 그래프는 유한 집합의 정점과 무순서쌍의 정점 집합으로 형성되며, 이를 간선이라고 한다. 그래프 의 클리크는 의 완전 부분 그래프이다. 즉, 는 의 간선 양 끝점이 되는 모든 두 정점으로 이루어진 정점의 부분 집합이다. 극대 클리크는 더 이상 정점을 추가할 수 없는 클리크이다.^[1] 최대 클리크는 가능한 가장 많은 정점을 포함하는 클리크이며, 클리크 수 는 의 최대 클리크에 있는 정점의 수이다.^[1]

표시된 그래프에는 최대 클리크 {1, 2, 5} 하나와 최대 클리크 {2, 3}, {3, 4}, {4, 5}, {4, 6} 네 개가 더 있다.

클리크 문제와 독립 집합 문제는 보완적이다. 의 클리크는 의 여 그래프에서 독립 집합과 같으며 그 반대도 성립한다.^[6]

3. 역사 및 응용

"클리크"라는 용어와 클리크를 찾는 문제는 사회 과학에서 비롯되었으며, 여기서 완전 부분 그래프는 서로 모두 아는 사람들로 구성된 사교 클리크를 모델링하는 데 사용되었다. 루스(Ruce)와 페리(Perry)는 소셜 네트워크를 모델링하기 위해 그래프를 사용했으며, 완전 부분 그래프를 "클리크"라고 처음 불렀다.^[1] 클리크 문제를 해결하기 위한 최초의 알고리즘은 해러리(Harary)와 로스(Ross)의 알고리즘이었으며, 사회학적 응용에 의해 동기 부여를 받았다.

해러리와 로스의 연구 이후, 많은 연구자들이 클리크 문제의 다양한 버전에 대한 알고리즘을 고안했다.^[1] 1970년대에는 최대 클리크 문제의 최악의 경우 복잡성에 대한 초기 연구가 진행되었다. 또한, 쿡(Cook)과 카프(Karp)의 연구를 시작으로 NP-완전성 이론 및 관련 난해성 결과를 사용하여 클리크 문제의 어려움에 대한 수학적 설명을 제공하기 시작했다. 1990년대에는 ( P ≠ NP라고 가정할 때) 문제를 정확하고 효율적으로 근사하는 것조차 불가능하다는 것이 밝혀졌다.

클리크 찾기 알고리즘은 화학, 생물 정보학, 자동 테스트 패턴 생성, 의존성 그래프 분석 등 다양한 분야에서 활용된다.

3. 1. 사회 연결망 분석

사회 연결망에서 클리크는 서로 모두 아는 사람들의 집단을 나타낸다.^[8] 사회 과학자들은 클리크 개념을 확장하여 다양한 연결 관계를 공유하는 "응집력 있는 하위 그룹"을 정의하였다. 대한민국 사회에서도 온라인 커뮤니티, 정치 집단, 학연, 지연 등 다양한 형태로 클리크가 존재하며, 사회적 자본 형성과 정보 확산에 중요한 역할을 한다.

3. 2. 화학 및 생물 정보학

화학에서 클리크 찾기 알고리즘은 분자 도킹, 화학 반응의 결합 부위 모델링, 유사 구조 탐색 등에 사용된다.^[2]^[3] 이러한 응용 분야에서는 각 정점이 두 분자 각각에서 일치하는 원자 쌍을 나타내는 그래프를 형성한다. 두 정점은 그들이 나타내는 일치가 서로 호환되는 경우(예: 두 분자 내의 원자 간 거리가 주어진 허용 오차 내에서 대략 같은 경우) 간선으로 연결된다. 이 그래프의 클리크는 모든 일치가 서로 호환되는 일치된 원자 쌍의 집합을 나타낸다.^[3] 이 방법의 특수한 경우는 두 그래프의 최대 공통 유도 부분 그래프를 찾는 문제를 해당 곱에서 최대 클리크를 찾는 문제로 줄이는 것이다.

생물 정보학에서 클리크 찾기 알고리즘은 진화 트리를 추론하고, 단백질 구조를 예측하고, 단백질의 긴밀하게 상호 작용하는 클러스터를 찾는 데 사용된다.

3. 3. 기타 응용

자동 테스트 패턴 생성에서 클리크를 찾아 테스트 집합 크기를 줄일 수 있다.^[4] 의존성 그래프에서 클리크를 나열하여 특정 임의 프로세스 분석을 수행할 수 있다.^[4] 켈러 추측의 반증에는 클리크 찾기 알고리즘이 사용되었다.

4. 알고리즘

클릭 문제를 해결하기 위한 다양한 알고리즘이 개발되었다. 임의의 ''n''개의 정점을 가진 그래프에서 최대 클릭을 찾는 문제는 그래프의 모든 최대 클릭을 나열하고 그 중 가장 큰 것을 선택하는 방식으로 시간 내에 해결할 수 있다. 그러나 이보다 더 효율적인 알고리즘도 존재한다.

타잔과 트로야노프스키(Tarjan, Trojanowski)는 1977년에 시간 내에 이 문제를 해결하는 알고리즘을 제시했다.^[15] 이 알고리즘은 Bron–Kerbosch 알고리즘과 유사한 재귀적 백트래킹 방식을 사용하지만, 최적의 해를 찾을 수 없는 경우 일부 재귀 호출을 제거하여 효율성을 높였다. 지안(Jian)은 1986년에 시간을 로 개선했고,^[16] 롭슨(Robson)은 1986년에 더 많은 공간을 사용하는 대신 시간을 로 개선했다.^[17] 롭슨의 알고리즘은 백트래킹 방식과 동적 프로그래밍 기법을 결합하여, 보완 그래프의 모든 작은 연결된 부분 그래프에 대한 최적해를 미리 계산하고 이를 사용하여 백트래킹 과정을 단축한다. 현재 알려진 가장 빠른 알고리즘은 롭슨(Robson)이 2001년에 제시한 방법의 개선된 버전으로, 시간 내에 실행된다.^[15]

최악의 경우 실행 시간 보장이 없는 최대 클릭 문제를 해결하기 위한 휴리스틱 알고리즘 연구도 활발하게 진행되었다. 분기 한정법,^[15] 지역 탐색,^[16] 탐욕 알고리즘,^[17] 제약 프로그래밍 등의 방법이 사용되었다. 또한, DNA 컴퓨팅^[18] 및 단열 양자 계산과 같은 비표준 컴퓨팅 방법론도 제안되었다. 최대 클릭 문제는 1992-1993년 DIMACS에서 주최한 구현 챌린지의 주제였으며,^[19] 이 챌린지를 위해 공개된 벤치마크 그래프 모음이 제공된다.

4. 1. 극대 클리크 찾기

단일 극대 클리크는 탐욕 알고리즘을 사용하여 선형 시간에 찾을 수 있다.

4. 2. 고정 크기 클리크 찾기

크기가 ''k''인 클릭을 찾는 무차별 대입 알고리즘은 모든 ''k''개 정점의 부분 집합을 확인하므로, O(''n''^''k'' ''k''²) 시간에 실행된다.^[15] ''k''가 고정된 상수이면 이 알고리즘은 다항 시간 안에 실행되지만, ''k''가 변하는 값이면 지수 시간이 걸린다.

''k'' = 3인 경우, 즉 삼각형 찾기 문제는 행렬 곱셈을 이용하여 O(''n''^2.376) 시간 안에 해결할 수 있다.^[15] Itai|이타이^영어와 Rodeh|로데^영어가 이 방법을 제시하였다.^[15] 1985년 Chiba|치바^영어와 Nishizeki|니시제키^영어는 아보리시티(arboricity) ''a''(''G'')를 이용하여 O(''m'' · ''a''(''G'')) 시간 안에 삼각형을 찾는 알고리즘을 제시하였다.^[15] 여기서 ''m''은 그래프의 변의 개수이다. 평면 그래프와 같이 아보리시티가 일정한 그래프에서는 이 알고리즘이 선형 시간에 실행된다.

4. 3. 모든 극대 클리크 나열

문과 모저(Moon and Moser)는 ''n''개의 정점을 가진 그래프가 최대 3^''n''/3개의 극대 클리크를 가질 수 있음을 보였다.^[15] Bron–Kerbosch 알고리즘은 재귀적 백트래킹을 통해 모든 극대 클리크를 나열하며, 최악의 경우 O(3^''n''/3) 시간이 걸린다.^[15] 츠키야마(Tsukiyama) 등은 1977년 생성된 클리크당 다항 시간 내에 모든 극대 클리크를 나열하는 출력 민감형 알고리즘을 제시했다.^[15] 치바(Chiba)와 니시제키(Nishizeki)는 이를 클리크당 O(''m'' * ''a''(G)) 시간으로 개선했다.^[15] 마키노(Makino)와 우노(Uno)는 빠른 행렬 곱셈을 기반으로 하는 대안적인 출력 민감형 알고리즘을 제공했다.^[15] 존슨(Johnson)과 야나카키스(Yannakakis)는 다항 지연으로 모든 극대 클리크를 사전식 순서로 나열할 수 있음을 보였다.^[15]

4. 4. 임의 그래프에서 최대 클리크 찾기

Tarjan과 트로야노프스키는 1977년에 O(2^''n''/3) 시간 알고리즘을 제시했다.^[15] Jian은 1986년에 O(2^0.304''n'')으로 개선했고,^[16] Robson은 더 많은 공간을 사용하여 O(2^0.276''n'')으로 개선했다.^[17] Robson의 알고리즘은 백트래킹과 동적 프로그래밍 기법을 결합한 방법이다. 현재 가장 빠른 알고리즘은 Robson의 방법을 개선한 것으로, O(2^0.249''n'') 시간에 실행된다.^[15]

분기 한정법,^[15] 지역 탐색,^[16] 탐욕 알고리즘,^[17] 및 제약 프로그래밍을 포함한 휴리스틱 알고리즘도 연구되었다. DNA 컴퓨팅,^[18] 단열 양자 계산^[15] 등 비표준 컴퓨팅 방법론도 제안되었다.

4. 5. 특수 그래프 클래스

평면 그래프는 최대 4개의 정점을 가진 클릭을 가지며, 선형 시간에 찾을 수 있다. 완전 그래프에서는 반정부 프로그램을 사용하여 다항 시간 안에 최대 클릭을 찾을 수 있다. 이분 그래프의 여 그래프에서는 매칭 기술을 사용하여 최대 클릭을 찾을 수 있다. 순열 그래프에서 최대 클릭은 최장 감소 부분 수열이며, 해당 알고리즘을 사용하여 찾을 수 있다. 현 그래프에서는 정점을 제거 순서로 나열하여 최대 클릭을 찾을 수 있다. 원 그래프, 단위 디스크 그래프 등에서도 특화된 알고리즘이 존재한다.

4. 6. 랜덤 그래프

에르되시-레니 모형에서 그려진 랜덤 그래프에서 최대 클리크를 찾는 문제는 Karp가 1976년에 제안했다.^[1] 랜덤 그래프의 최대 클리크는 높은 확률로 로그 크기를 가지며, 준 다항 시간에 찾을 수 있다.^[1] 심어진 클릭 문제는 큰 클릭을 추가하여 보강된 랜덤 그래프에 대한 클릭 문제이다.^[1] 스펙트럼 그래프 이론 및 반정부 프로그램은 크기가 $ \Omega(\sqrt{n}) $인 숨겨진 클릭을 감지할 수 있지만, 더 작은 크기의 숨겨진 클릭을 감지하는 다항 시간 알고리즘은 알려져 있지 않다.^[1]

5. 계산 복잡도

Tarjan과 Trojanowski는 Bron–Kerbosch 알고리즘과 유사한 재귀적 백트래킹 방식으로 최대 클릭 문제를 시간 내에 해결하는 알고리즘을 제시했다. 이 알고리즘은 호출 내에서 발견된 클릭이 최적이 아님을 보일 수 있을 때 일부 재귀 호출을 제거한다.^[27] Jian은 이 시간을 로 개선했고, Robson은 더 많은 공간을 사용하는 대신 시간을 로 개선했다. 롭슨의 알고리즘은 유사한 백트래킹 방식과 동적 프로그래밍 기법을 결합하여, 보완 그래프의 모든 작은 연결된 부분 그래프에 대해 최적의 해를 미리 계산하고 이를 통해 백트래킹 재귀를 단축한다. 현재 알려진 가장 빠른 알고리즘은 롭슨의 방법을 개선하여 시간 내에 실행된다.^[19]

최대 클릭 문제를 해결하기 위해 최악의 경우 실행 시간 보장이 없는 휴리스틱 알고리즘에 대한 연구도 광범위하게 진행되었다. 여기에는 분기 한정법,^[15] 지역 탐색,^[16] 탐욕 알고리즘,^[17] 제약 프로그래밍 등 다양한 방법이 사용된다.^[19] DNA 컴퓨팅,^[18] 단열 양자 계산^[19]과 같은 비표준 컴퓨팅 방법론도 클릭을 찾는 데 제안되었다. 최대 클릭 문제는 1992–1993년 DIMACS에서 후원하는 구현 챌린지의 주제였으며,^[19] 이 챌린지를 위한 벤치마크 그래프 모음이 공개적으로 제공된다.^[19]

5. 1. NP-완전성

클리크 결정 문제는 NP-완전이다. 이 문제는 리처드 카프가 1972년 논문 "조합 문제 간의 환원 가능성"에서 NP-완전임을 보인 카프의 21개의 NP-완전 문제 중 하나이다.^[27] 스티븐 쿡의 NP-완전 문제 이론을 소개하는 논문에서도 언급되었다.^[26] 결정 문제의 어려움 때문에 최대 클리크를 찾는 문제 또한 NP-어렵다. 만약 이 문제를 풀 수 있다면, 최대 클리크의 크기를 결정 문제에서 주어진 크기 매개변수와 비교하여 결정 문제 또한 풀 수 있다.

카프의 NP-완전성 증명은 불만족 문제에서 다대일 환원을 사용한다. 이 증명은 결합 정규 형식 (CNF)의 부울 공식을 최대 클리크 문제의 동등한 인스턴스로 변환하는 방법을 설명한다.^[27] 만족성 문제는 쿡-레빈 정리에서 NP-완전으로 증명되었다. 주어진 CNF 공식에서 카프는 각 쌍 (''v'',''c'')|v, c^영어에 정점을 하나씩 가진 그래프를 구성하는데, 여기서 v|v^영어는 변수 또는 그 부정이고, c|c^영어는 v|v^영어를 포함하는 공식의 절이다. 이 정점들 중 두 개는 서로 다른 절에 대한 호환 가능한 변수 할당을 나타내는 경우, 즉 (''v'',''c'')|v, c^영어에서 (''u'',''d'')|u, d^영어로의 간선이 존재하며, 이는 ''c'' ≠ ''d''|c ≠ d^영어이고 u|u^영어와 v|v^영어가 서로의 부정 관계가 아닐 때이다. 만약 k|k^영어가 CNF 공식의 절 수를 나타낸다면, 이 그래프에서 k|k^영어-정점 클리크는 공식을 만족시키기 위해 변수에 진리값을 할당하는 일관된 방식을 나타낸다. 따라서 공식은 k|k^영어-정점 클리크가 존재할 경우에만 만족 가능하다.^[27]

일부 NP-완전 문제 (예: 평면 그래프에서의 외판원 문제)는 입력 크기 매개변수 n|n^영어의 아선형 함수의 지수 시간 내에 풀릴 수 있으며, 이는 무차별 대입 검색보다 훨씬 빠르다.^[28] 그러나 임의의 그래프에서 클리크 문제에 대해 이러한 아지수 시간 경계가 가능할 가능성은 낮으며, 이는 다른 많은 표준 NP-완전 문제에도 유사한 아지수 경계를 의미하기 때문이다.^[26]

5. 2. 회로 복잡도

클릭 문제는 회로 복잡도에서 여러 하한을 증명하는 데 사용되었다. 주어진 크기의 클릭 존재 여부는 단조 그래프 속성을 가지는데, 이는 주어진 그래프에 클릭이 존재하면 모든 슈퍼그래프에도 존재함을 의미한다.^[29] 이 속성은 단조적이므로, 주어진 고정된 클릭 크기에 대한 클릭 결정 문제를 해결하기 위해 AND 게이트와 OR 게이트만 사용하는 단조 회로가 존재해야 한다. 그러나 이러한 회로의 크기는 정점 수와 클릭 크기의 초다항식 함수, 즉 정점 수의 세제곱근에서 지수적으로 증가하는 것으로 증명될 수 있다.^[29] NOT 게이트가 소수 허용되더라도 복잡성은 초다항식으로 유지된다.^[30] 또한, 제한된 팬인의 게이트를 사용하는 클릭 문제에 대한 단조 회로의 깊이는 클릭 크기에 대한 다항식 이상이어야 한다.^[31]

5. 3. 의사 결정 트리 복잡도

클리크를 포함하는 속성은 단조적이므로 Aanderaa–Karp–Rosenberg 추측에 의해 결정론적 의사 결정 트리 복잡성은 n(n-1)/2이다.^[32] 이는 모든 그래프 속성이 최대 n(n-1)/2개의 질문으로 결정될 수 있음을 의미한다.

Aanderaa–Karp–Rosenberg 추측은 비자명한 단조 함수의 임의 의사 결정 트리 복잡성이 라고 명시한다. 2 ≤ k ≤ n에 대해 k-클리크를 포함하는 속성은 임의 의사 결정 트리 복잡성이 인 것으로 알려져 있다.^[34]

양자 의사 결정 트리의 경우 가장 잘 알려진 하한은 이지만, k ≥ 3의 경우 일치하는 알고리즘은 알려져 있지 않다.^[35]

5. 4. 고정 매개변수 난해성

Clique^영어 문제는 매개변수 ''k'' (클릭 크기)에 대해 고정 매개변수 다루기 어렵다(W[1]-완전).^[36]는 고정 매개변수 추적 가능한 알고리즘이 없을 것이라고 추측되는 매개변수화된 문제의 계층 구조인 W 계층 구조를 정의했다. 그들은 독립 집합(또는 이에 상응하는 클리크)이 이 계층 구조의 첫 번째 수준인 W[1]에 대해 어렵다는 것을 증명했다. 따라서 그들의 추측에 따르면 클리크는 고정 매개변수 추적 가능한 알고리즘이 없다.^[36] 또한 이 결과는 다른 많은 문제의 W[1]-경도의 증거의 기초를 제공하며, 따라서 매개변수화된 복잡도에 대한 쿠크-레빈 정리의 유사 역할을 한다.^[36]

지수 시간 가설 하에서, ''k''-정점 클리크는 시간 내에 수행될 수 없다.^[36]는 지수 시간 가설이 실패하지 않는 한, ''k''-정점 클리크를 시간 내에 수행할 수 없다는 것을 보여주었다. 다시 말해, 이것은 고정 매개변수 추적 가능한 알고리즘이 불가능하다는 증거를 제공한다.^[36]

5. 5. 근사 난이도

P = NP가 아닌 한, 임의의 ε > 0에 대해 O(''n''^{1 − ''ε''})보다 나은 계수로 최대 클리크를 근사하는 다항 시간 알고리즘은 존재할 수 없다.^[39] 이러한 근사 불가능성 결과는 확률적 검증 증명 시스템을 클리크 문제로 변환하여 증명된다.^[40]

이 증명 방법의 핵심은 부울 만족 문제와 같은 NP-완전 문제에 대한 확률적 검증 증명 시스템을 나타내는 그래프를 만드는 것이다. 확률적 검증 증명 시스템에서 증명은 일련의 비트들로 표현된다. 만족 문제 인스턴스는 만족 가능한 경우에만 유효한 증명을 갖는다. 증명은 만족 문제에 대한 입력에 대해 다항 시간 계산을 거친 후, 증명 문자열에서 무작위로 선택된 몇몇 위치들을 검사하는 알고리즘에 의해 확인된다. 검사기는 선택된 비트들의 값에 따라 나머지 비트를 확인하지 않고 증명을 수락하거나 거부한다. 거짓 음성(false negative)은 허용되지 않아 유효한 증명은 항상 수락되어야 하지만, 유효하지 않은 증명은 때때로 실수로 수락될 수 있다. 이때, 모든 유효하지 않은 증명에 대해 검사기가 증명을 수락할 확률은 낮아야 한다.^[40]

이러한 확률적 검증 증명 시스템을 클릭 문제로 변환하기 위해, 증명 검사기의 각 가능한 수락 실행에 대한 정점을 갖는 그래프를 만든다. 즉, 각 정점은 검사할 위치 집합의 가능한 무작위 선택 중 하나와, 검사기가 증명을 수락하게 하는 해당 위치에 대한 비트 값으로 정의된다. 이는 각 검사된 위치에는 0 또는 1, 나머지 위치에는 와일드카드 문자가 있는 부분 단어로 표현할 수 있다. 두 정점은 해당 두 수락 실행이 둘 다 검사하는 모든 위치에서 동일한 비트 값을 가질 때, 이 그래프에서 서로 인접한다. 각 (유효하거나 유효하지 않은) 증명 문자열은 해당 증명 문자열을 확인하는 수락 실행들의 집합인 클리크에 해당하며, 모든 최대 클리크는 이러한 방식으로 만들어진다. 만약 어떤 클리크가 많은 증명 검사기가 수락하는 증명 문자열에 해당한다면, 그 클리크는 크다. 원래 만족 가능성 인스턴스가 만족 가능하다면, 모든 검사기 실행에 의해 수락되는 유효한 증명 문자열이 존재하고, 이 문자열은 그래프에서 큰 클리크에 해당한다. 그러나 원래 인스턴스가 만족 가능하지 않다면, 모든 증명 문자열은 유효하지 않고, 각 증명 문자열은 그것을 실수로 수락하는 검사기 실행이 적으므로, 모든 클리크는 작다. 따라서 큰 클리크를 갖는 그래프와 모든 클리크가 작은 그래프를 다항 시간 안에 구별할 수 있거나, 클리크 문제를 정확하게 근사할 수 있다면, 만족 가능성 인스턴스에서 생성된 그래프에 이 근사를 적용하여 만족 가능한 인스턴스와 만족 불가능한 인스턴스를 구별할 수 있게 된다. 하지만 P = NP가 아니라면 이것은 불가능하다.^[40]

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

6. 한국 사회에 미치는 영향 및 윤리적 고려 사항

클리크는 더 큰 클리크에 포함되지 않는 극대 클리크를 의미하기도 한다.^[8] 모든 클릭은 극대 클릭에 포함되지만, 모든 극대 클릭이 최대 클릭(가장 큰 클릭)인 것은 아니다. 극대 클릭은 찾기 쉽고 크기가 작을 수 있지만, 최대 클릭이나 큰 클릭을 찾는 문제는 더 어렵기 때문에 많은 연구가 이루어졌다.^[9]

6. 1. 긍정적 측면

클리크는 사회적 자본을 형성하고, 정보를 공유하며, 협력을 증진하는 등 긍정적인 역할을 할 수 있다. 특히, 위기 상황에서 클리크는 빠른 정보 전파와 문제 해결에 기여할 수 있다. 중도진보적 관점에서 볼 때, 클리크는 사회적 연대를 강화하고 공동체 의식을 함양하는 데 도움이 될 수 있다.

6. 2. 부정적 측면

클리크는 배타성, 집단 이기주의, 불공정 경쟁 등을 야기할 수 있다. 특히 권력형 클리크는 사회적 불평등을 심화시키고 부정부패의 온상이 될 수 있다. 더불어민주당은 과거 "최순실-박근혜 게이트"와 같이 권력형 클리크의 폐해를 강력하게 비판해 왔다.

온라인 커뮤니티의 클리크는 확증 편향, 집단 극단화, 사이버 폭력 등 문제를 야기할 수 있다. 일부 극우 성향 온라인 커뮤니티(예: 일베저장소)는 사회적 갈등을 조장하고 혐오 표현을 확산시키는 클리크로 작용할 수 있다.

참조

_[1] 서적
_[2] 서적 https://books.google[...]
_[3] 서적 https://books.google[...]
_[4] 서적
_[5] 서적
_[6] 서적
_[7] 서적
_[8] 서적
_[9] 서적 https://books.google[...]
_[10] 서적
_[11] 서적
_[12] 서적
_[13] 서적
_[14] 서적
_[15] 서적
_[16] 서적
_[17] 서적
_[18] 서적
_[19] 웹사이트 DIMACS challenge graphs for the clique problem http://dimacs.rutger[...] 2018-03-30
_[20] 서적
_[21] 서적
_[22] 서적
_[23] 서적
_[24] 서적
_[25] 서적
_[26] 서적
_[27] 서적
_[28] 서적
_[29] 서적
_[30] 서적
_[31] 서적
_[32] 서적
_[33] 서적
_[34] 서적
_[35] 서적
_[36] 논문 1999
_[37] 논문 2013
_[38] 논문 1991
_[39] 논문 1999
_[40] 논문 1991

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

문의하기 : help@durumis.com