Static Wikipedia February 2008 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu

Web Analytics
Cookie Policy Terms and Conditions Co-NP - 위키백과

Co-NP

위키백과 ― 우리 모두의 백과사전.

계산 복잡도 이론에서 co-NP복잡도 종류이다. 문제 \mathcal{X}co-NP에 들어 있다는 것은 그 보완 문제인 \overline{\mathcal{X}}NP에 속한다는 것과 동치이다. 간단히 말하면, co-NP아니오 보기(반례라고도 한다)에 대해 효율적으로 검증할 수 있는 증명이 있는 문제의 집합이다.

NP-완전 문제 중 부분집합 합 문제가 있다. 이 문제는 정수 유한집합이 있을 때, 이 집합의 공집합이 아닌 부분집합 중 원소를 다 더하면 0이 되는 것이 있는지를 묻는 문제이다. 이 문제의 보완 문제는 co-NP에 들어가는데, 정수 유한집합이 주어질 때, 공집합이 아닌 부분집합은 모두, 원소를 다 더했을 때 0이 아닌지를 묻는 문제가 된다. "아니오" 보기에 대한 증명을 하려면, 합이 0이 되고 공집합이 아닌 부분집합을 찾아야 한다. 그렇게 하면 이 증명은 검증하기 쉬워진다.

다항 시간에 풀 수 있는 문제인 PNPco-NP 모두의 부분집합이다. P는 두 경우 모두 진부분집합일 것으로 추측하고 있다. (한쪽만 진부분집합이고, 다른 쪽은 아닌 경우는 불가능함을 보일 수 있다.) NPco-NP 역시, 같은 집합이 아닐 것이다. 만약 그렇지 않다ng면, NP-완전 문제가 co-NP에 들어갈 수 있고, co-NP-완전 문제가 NP에 들어갈 수 있기 때문이다.

이는 다음과 같이 보일 수 있다. co-NP에 들어가는 NP-완전 문제가 있다고 하자. 모든 NP 문제는 이 문제로 환산할 수 있기 때문에, 각 NP문제에 대해서 그 보완 문제를 다항 시간에 판정할 수 있는 비결정적인 튜링 기계를 만들 수 있다. 다시 말해서, NPco-NP의 부분집합이 된다. 따라서 NP 문제의 보완을 모은 집합이 co-NP 문제의 보완을 모은 집합의 부분집합이 된다. 곧, co-NPNP의 부분집합이 된다. 앞에서 NPco-NP의 부분집합임을 보였으므로, 이는 두 집합이 같다는 뜻이 된다. co-NP-완전 문제가 NP일 수 없음을 보이는 증명은 이 증명과 대칭을 이룬다.

어떤 문제가 NPco-NP 둘 다 된다는 것을 보였다면, 이는 그 문제가 NP-완전이 아닐 것이라는 강력한 증거가 된다. (NP-완전이라면 NP = co-NP이기 때문)

정수 소인수분해 문제는 NPco-NP에 모두 들어가는, 유명한 문제이다. 양의 정수 mn이 있을 때 mn보다 작고 1보다 큰 약수가 있는지를 묻는다. 있는 경우를 보이는 쪽은 쉽다. m에 그런 약수가 있다면, 그 약수로 나누어 보면 된다. 반대쪽은 좀 어려운데, 그런 약수가 없다는 것을 보이려면 일일이 나누어 보아야 한다.

소인수분해 문제를 소수 문제와 헷갈리는 사람이 많다. 소수 문제도 소인수분해 문제처럼 NPco-NP 둘 다에 들어간다. 그러나 아직 확실치 않은 소인수분해하고는 달리, 소수 문제는 P이다. [1]

[편집] 외부 링크

[편집] 참고 문헌

  1. ((영어)) 소수 문제가 P임을 밝힌 논문


주요 복잡도 종류 (더 보기)

P | NP | co-NP | NP-C | co-NP-C | NP-난해 | UP | #P | #P-C | L | NL | NC | P-C | PSPACE | PSPACE-C
EXPTIME | EXPSPACE | PR | RE | co-RE | RE-C | co-RE-C | R | BQP | BPP | RP | ZPP | PCP | IP | PH

Static Wikipedia 2008 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu -

Static Wikipedia 2007 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu -

Static Wikipedia 2006 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu