1-3
클릭
clique
서로 빠짐없이 이어진 점들의 모임
그래프에서 어느 두 꼭짓점을 골라도 변으로 이어져 있는 꼭짓점 집합이다. 사람 관계 그래프라면 서로 모두 아는 사이인 무리다. 「크기가 k 인 클릭이 있는가」는 NP-완전이고, 정점 덮개·독립 집합 문제와 간단한 환산으로 오간다. 라즈보로프가 1985년에 단조 회로로는 클릭 문제를 다항 크기로 풀 수 없음을 증명해, 회로 하한 연구의 대표 결과가 되었다.
clique
서로 빠짐없이 이어진 점들의 모임
그래프에서 어느 두 꼭짓점을 골라도 변으로 이어져 있는 꼭짓점 집합이다. 사람 관계 그래프라면 서로 모두 아는 사이인 무리다. 「크기가 k 인 클릭이 있는가」는 NP-완전이고, 정점 덮개·독립 집합 문제와 간단한 환산으로 오간다. 라즈보로프가 1985년에 단조 회로로는 클릭 문제를 다항 크기로 풀 수 없음을 증명해, 회로 하한 연구의 대표 결과가 되었다.