여 NP

여 NP(co-NP)는 계산 복잡도 이론의 복잡도 종류이다. 반례에 대해 효율적으로 검증할 수 있는 증명이 있는 문제의 집합이기도하다.

개요

문제 ${\mathcal {X}}$가 여 NP에 들어 있다는 것은 그 보완 문제인 ${\overline {\mathcal {X}}}$가 NP에 속한다는 것과 동치관계이다. 간단히 말하면, 여 NP는 반례에 대해 효율적으로 검증할 수 있는 증명이 있는 문제의 집합이다. NP-완전 문제 중 부분집합 합 문제가 있다. 이 문제는 정수 유한집합이 있을 때, 이 집합의 공집합이 아닌 부분집합 중 원소를 다 더하면 0이 되는 것이 있는지를 묻는 문제이다. 이 문제의 보완 문제는 여 NP에 들어가는데, 정수 유한집합이 주어질 때 공집합이 아닌 부분집합은 모두 원소를 다 더했을 때 0이 아닌지를 묻는 문제가 된다. '아니오' 보기에 대한 증명을 하려면, 합이 0이 되고 공집합이 아닌 부분집합을 찾아야 한다. 그렇게 하면 이 증명은 검증하기 쉬워진다.

특징

다항 시간에 풀 수 있는 문제인 P는 NP와 여 NP 모두의 부분집합이다. P는 두 경우 모두 진부분집합일 것으로 추측하고 있다. 한쪽만 진부분집합이고, 다른 쪽은 아닌 경우는 불가능함을 보일 수 있다. NP와 여 NP 역시 같은 집합이 아닐 것이다. 만약 그렇지 않다면, NP-완전 문제가 여 NP에 들어갈 수 있고, 여 NP-완전 문제가 NP에 들어갈 수 있기 때문이다. 예를 들어-NP에 들어가는 NP-완전 문제가 있다고 하자. 모든 NP 문제는 이 문제로 환산할 수 있기 때문에, 각 NP 문제에 대해서 그 보완 문제를 다항 시간에 판정할 수 있는 비결정적인 튜링 기계를 만들 수 있다. 다시 말해서, NP가 여 NP의 부분집합이 된다. 따라서 NP 문제의 보완을 모은 집합이 여 NP 문제의 보완을 모은 집합의 부분집합이 된다. 곧, 여 NP가 NP의 부분집합이 된다. 앞에서 NP가 여 NP의 부분집합임을 보였으므로, 이는 두 집합이 같다는 뜻이 된다. 여 NP-완전 문제가 NP일 수 없음을 보이는 증명은 이 증명과 대칭을 이룬다. 또한 어떤 문제가 NP와 여 NP 둘 다 된다는 것을 보였다면, 이는 그 문제가 NP-완전이 아닐 것이라는 강력한 증거가 된다. NP-완전이라면 NP = 여 NP이기 때문이다. 정수의 소인수 분해 문제는 NP와 여 NP에 모두 들어가는, 유명한 문제이다. 양의 정수 $m$과 $n$이 있을 때 $m$에 $n$보다 작고 1보다 큰 약수가 있는지를 묻는다. 있는 경우를 보이는 쪽은 쉽다. $m$에 그런 약수가 있다면, 그 약수로 나누어 보면 된다. 반대쪽은 좀 어려운데, 그런 약수가 없다는 것을 보이려면 일일이 나누어 보아야 한다. 소인수 분해 문제를 소수 문제와 헷갈리는 사람이 많다. 소수 문제도 소인수 분해 문제처럼 NP와 여 NP 둘 다에 들어간다. 그러나 아직 확실치 않은 소인수 분해와는 달리, 소수 문제는 P이다.

참고자료

• 여 NP 위키백과- https://ko.wikipedia.org/wiki/Co-NP)

같이 보기

• NP
• 여 NP-완전

이 여 NP 문서는 인공지능 기술에 관한 토막글입니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 이 문서의 내용을 채워주세요.

인공지능 : 인공지능 기술 □■⊕, 인공지능 활용, 인공지능 개발업체, 인공지능 인물 인간적 행위 로봇공학 • 로봇기술 • 인지과학 • 자동추론 • 자연어 처리 • 지식표현 • 컴퓨터 비전 • 튜링 테스트 합리적 사고 결정이론 • 논리학 • 논리주의자 • 삼단논법 • 선호도 • 최대기대효용 • 효용이론 강화학습 ADP • DDPG • DQN • SARSA • 결정이론적 메타추론 • 계통적 강화학습 • 동적 계획법 • 모델 기반 강화학습 • 모델 프리 강화학습 • 반영식 아키텍처 • 수시 알고리즘 • 심층믿음망 • 어니 • 에이전트 • 확률적 경사하강법 인공지능 프로그램 A2I • 어니 • 알파고 • 알파고제로 • 왓슨 • 카페 • 텐서플로 • 토치 • 한돌 인공지능 알고리즘 AGI • 관계형 네트워크(RN) • 다층퍼셉트론 • 데이터마이닝 • 딥러닝 • 딥큐러닝 • 머신러닝(기계학습) • 방사신경망 • 분산 샌드박스 • 비지도학습 • 생성대립신경망(GAN) • 생성형 AI • 수퍼 얼라인먼트 • 순전파 • 순환신경망(RNN) • 시그노이드 함수 • 신경망 구조 • 심층신경망(DNN) • 심층신뢰신경망(DBN) • 양방향 비고정값 암호 체계(TSID) • 역전파 • 인공신경망(ANN) • 인공지능(AI) • 제한 볼츠만 머신(RBM) • 전방전달신경망 • 지도학습 • 코헨 자기조직 신경망 • 텍스트마이닝 • 파이 • 퍼셉트론 • 합성곱 신경망(CNN) 문자인식 ICR • OCR • OMR • 문자인식 인공지능 특징 계산상의 합리성 • 분산성 • 불확실성 • 예측곤란성 • 완벽한 합리성 • 유계 합리성 • 이유 불충분의 원리 • 자율성 • 할루시네이션 계산 복잡도 NP • NP-완전 • 공간복잡도 • 시간복잡도 • 여 NP • 여 NP-완전 인공지능 기술 BCI • GPT • 딥블루 • 딥페이크 • 멀티모달 • 모달 • 모달리티 • 모달창 • 알렉스넷 • 왓슨 • 텔레파시 • 환각 인공지능 법적 지위 권리주체성 • 전자대리인 • 전자적 인간 • 책임법 • 코파일럿 인공지능 업무 데이터라벨러 • 데이터라벨링 • 크라우드워커 위키 : 자동차, 교통, 지역, 산업, 기업, 단체, 업무, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반