이것은 로그 공간에서 NP- 완료 크리크 문제 를 해결할 수 있는지 묻는 것처럼 들립니다 . 튜링 머신을 사용하면 하나의 테이프 만 읽기 전용이며 입력 그래프를 저장합니다. 다른 테이프는 일부 상수 사용 가능한 공간이 있도록 됩니다. 이 모델에서 해결할 수있는 문제의 클래스를 결정 론적 로그 공간 이라고 합니다. ( wikipedia 또는 복잡한 동물원 참조 )clgn

$c\lg n$

$c \lg n$c

$c$

$c$L

$L$

$L$

인지 여부는 알 수 없지만 긍정적 인 대답은 임을 암시 하므로 답을 찾지 못할 것입니다. 및 의미 의미, .CLIQUE∈L

$\mathrm{C}\mathrm{L}\mathrm{I}\mathrm{Q}\mathrm{U}\mathrm{E}\in L$

$\mathrm{CLIQUE} \in L$P=NP

$P=NP$

$P = NP$L⊆P⊆NP

$L\subseteq P\subseteq NP$

$L \subseteq P \subseteq NP$CLIQUE∈L

$\mathrm{C}\mathrm{L}\mathrm{I}\mathrm{Q}\mathrm{U}\mathrm{E}\in L$

$\mathrm{CLIQUE} \in L$CLIQUE∈P

$\mathrm{C}\mathrm{L}\mathrm{I}\mathrm{Q}\mathrm{U}\mathrm{E}\in P$

$\mathrm{CLIQUE} \in P$P=NP

$P=NP$

$P = NP$

---

문제를 잘못 해석 한 경우 편집 :

당신하고자하면 그 에서 도당 크기와 동일 (즉, 입력과 메모리 규모의 양 후 단순 브 루트 포스 알고리즘있다) 할 수 있습니다 루프를 통해 모든 노드 의 가능한 세트를 설정 하고 -clique 를 형성하는지 확인하십시오 . 더 나은 솔루션을 찾기위한 출발점은 [1]의 참조 일 수 있습니다.k

$k$

$k$lgnk=klgn

$\lg n^k=k\lg n$

$\lg n^k = k \lg n$k

$k$

$k$k

$k$

$k$k

$k$

$k$k

$k$

$k$

---

[1] Virginia Vassilevska, “도둑질 문제에 대한 효율적인 알고리즘” pdf 링크

---

답변