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

[접기]인공지능 : 인공지능 서비스, 인공지능 모델, 인공지능 데이터, 인공지능 기술 □■⊕, 인공지능 로봇, 인공지능 기업, 인공지능 인물, 인공지능 역사 인공지능 기술 AGI • ANI • ASI • AI 워싱 • 감각 • 감성 • 강인공지능 • 개성 • 결정 • 다중 에이전트 • 데이터마이닝 • 동작 • 디지털 휴먼 • 로봇공학 • 로봇기술 • 마음 • 메타인지 • 무의식 • 미각 • 생각 • 선택 • 설명 • 설명가능 인공지능(XAI) • 성격 • 시각 • 약인공지능 • 에이전트 • 예측 • 오감 • 의도 • 의식 • 의지 • 이해 • 인성 • 자동추론 • 자아 • 자의식 • 전문가 혼합 • 정체성 • 제어 • 제어이론 • 지각 • 지능 • 지성 • 지식 • 지혜 • 청각 • 초인공지능 • 촉각 • 추론 • 추천 • 추천 알고리즘 • 킬 스위치 • 태도 • 튜링 테스트 • 판단 • 프롬프트 • 프롬프트 엔지니어링 • 해석 • 행동 • 행위 • 활동 • 후각 문자인식과 음성인식 ICR • MRC(기계독해) • OCR • OMR • URL • 감정 • 감정분석 • 개념 • 글자 • 기호 • 단어 • 답변 • 대화 • 동영상 • 디자인 • 말투 • 맥락 • 문단 • 문서 • 문자 • 문자인식 • 문자채팅 • 문장 • 발음 • 번역 • 부호 • 분류 • 사투리 • 상담 • 소스코드 • 스토리 • 억양 • 언어 • 영어 • 요청 • 음성 • 음성인식(STT) • 음성채팅 • 음성합성(TTS) • 응답 • 의미 • 이모지 • 이모티콘 • 이미지 • 인공어 • 인공지능 음성 • 인식 • 인지 • 인지과학 • 일본어 • 자막 • 자연어 • 자연어 이해 • 자연어 처리 • 중국어 • 질문 • 질의 • 질의응답 • 채팅 • 출처 • 코드 • 코딩 • 텍스트 • 통번역 • 통역 • 파일 • 패턴인식 • 폴더 • 표준어 • 한국어 • 화상채팅 • 화자인식 이미지 인식 딥페이크 • 바운딩박스 • 배경 • 배경인식 • 사물 • 사물인식 • 앵커박스 • 얼굴 • 얼굴인식 • 욜로(YOLO) • 이미지 보정 • 이미지 복원 • 이미지 분할 • 지문 • 지문인식 • 컴퓨터 비전 • 표정 • 표정인식 • 홍채 • 홍채인식 계산복잡도 NP • NP-완전 • 계산복잡도 • 공간복잡도 • 시간복잡도 • 여 NP • 여 NP-완전 인공지능 장비 AI 가속기 • AI칩 • GPU • 그래픽카드 • 레니게이드 • 마이아100 • 반도체 • 블랙웰 • 엔비디아 A100 • 엔비디아 H100 • 엔비디아 H20 • 엔비디아 H200 • 엔비디아 H800 • 워보이 • 집적회로(칩) • 코발트100 인공지능 특징 결정이론 • 계산상의 합리성 • 논리학 • 논리주의자 • 분산성 • 불확실성 • 삼단논법 • 선호도 • 예측곤란성 • 완벽한 합리성 • 유계 합리성 • 이유 불충분의 원리 • 자율성 • 최대기대효용 • 할루시네이션 • 효용이론 인공지능 법적 지위 권리주체성 • 소버린 AI • 전자대리인 • 전자적 인간 • 책임법 위키 : 인공지능, 개발, 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인물, 행사, 일반