計算 複雜度 理論 에서 co-NP 는 複雜度 種類 이다. 問題 ${\displaystyle {\mathcal {X}}}$가 co-NP 에 들어 있다는 것은 그 補完 문제인 ${\displaystyle {\overline {\mathcal {X}}}}$가 NP 에 屬한다는 것과 童穉이다. 簡單히 말하면, co-NP 는 아니오 보기( 泮隷 라고도 한다)에 對해 效率的으로 檢證할 수 있는 證明이 있는 問題의 集合이다.

NP-完全 問題 中 部分集合 合 問題 가 있다. 이 問題는 精髓 有限集合이 있을 때, 이 集合의 空集合이 아닌 部分集合 中 元素를 다 더하면 0이 되는 것이 있는지를 묻는 問題이다. 이 問題의 補完 問題는 co-NP에 들어가는데, 淨水 有限集合이 주어질 때, 空集合이 아닌 部分集合은 모두, 元素를 다 더했을 때 0이 아닌지를 묻는 問題가 된다. "아니오" 보기에 對한 證明을 하려면, 合이 0이 되고 空集合이 아닌 部分集合을 찾아야 한다. 그렇게 하면 이 證明은 檢證하기 쉬워진다.

다항 時間에 풀 수 있는 問題인 P 는 NP 와 co-NP 모두의 部分集合이다. P 는 두 境遇 모두 眞部分集合日 것으로 推測하고 있다. (한쪽만 眞部分集合이고, 다른 쪽은 아닌 境遇는 不可能함을 보일 수 있다.) NP 와 co-NP 亦是, 같은 集合이 아닐 것이다. 萬若 그렇지 않다면, NP-完全 問題가 co-NP 에 들어갈 수 있고, co-NP-完全 問題가 NP 에 들어갈 수 있기 때문이다.

이는 다음과 같이 보일 수 있다. co-NP 에 들어가는 NP-完全 問題가 있다고 하자. 모든 NP 問題는 이 問題로 換算할 수 있기 때문에, 各 NP 問題에 對해서 그 補完 問題를 다항 時間에 判定할 수 있는 非決定的인 튜링 機械를 만들 수 있다. 다시 말해서, NP 가 co-NP 의 部分集合이 된다. 따라서 NP 問題의 補完을 모은 集合이 co-NP 問題의 補完을 모은 集合의 部分集合이 된다. 곧, co-NP 가 NP 의 部分集合이 된다. 앞에서 NP 가 co-NP 의 部分集合임을 보였으므로, 이는 두 集合이 같다는 뜻이 된다. co-NP-完全 問題가 NP 일 수 없음을 보이는 證明은 이 證明과 對稱을 이룬다.

어떤 問題가 NP 와 co-NP 둘 다 된다는 것을 보였다면, 이는 그 問題가 NP-完全 이 아닐 것이라는 强力한 證據가 된다. ( NP-完全 이라면 NP = co-NP 利器 때문)

정수의 素因數 分解 問題는 NP 와 co-NP 에 모두 들어가는, 有名한 問題이다. 陽의 精髓 m 과 n 이 있을 때 m 에 n 보다 작고 1보다 큰 藥水가 있는지를 묻는다. 있는 境遇를 보이는 쪽은 쉽다. m 에 그런 藥水가 있다면, 그 藥水로 나누어 보면 된다. 反對쪽은 좀 어려운데, 그런 藥水가 없다는 것을 보이려면 一一이 나누어 보아야 한다.

素因數 分解 問題를 少數 問題와 헷갈리는 사람이 많다. 少數 問題도 素因數 分解 問題처럼 NP 와 co-NP 둘 다에 들어간다. 그러나 아직 確實치 않은 素因數 分解와는 달리, 少數 問題는 P 이다. ^[1]

外部 링크 [ 編輯 ]

• (英語) 複雜度 動物園 co-NP 우리

參考 文獻 [ 編輯 ]