여 NP-완전

여 NP-완전(co-NP-complete)은 여 NP에서 가장 어려운 문제의 집합을 말한다. 여기서 어렵다는 것은, P에 들어갈 가능성이 낮다는 뜻이다. 한 여 NP-완전 문제를 빠르게 푸는 방법을 찾아낸다면, 그 방법을 써서 모든 여 NP-완전 문제를 빠르게 풀 수 있게 된다.

정의

결정 문제 $C$가 여 NP에 속하며, 모든 여 NP 문제를 $C$로 다항 시간 내에 변환할 수 있다면, C는 여 NP-완전이라고 한다. 이는 모든 여 NP 문제 $L$에 대해, $L$에 대한 예제를 $C$에 대한 예제로 변환할 수 있는 다항 시간 알고리즘이 존재함을 의미한다. 따라서 $C$를 다항 시간 내에 해결할 수 있는 알고리즘이 있다면, 모든 여 NP 문제를 다항 시간 내에 해결할 수 있게 된다.

대표적인 여 NP-완전 문제로는 항진 명제 문제가 있다. 이는 주어진 논리식이 모든 변수 값의 조합에 대해 항상 참인지 판별하는 문제이다. 즉, 변수에 참 또는 거짓 값을 어떤 방식으로 대입하더라도 논리식 전체가 참이 되어야 한다. 이 문제는 불만족성 문제와 밀접한 관련이 있다. 불만족성 문제는 논리식이 참이 되는 변수값 할당이 존재하는지를 판별하는 문제인 반면, 항진 명제 문제는 모든 변수값 할당에 대해 논리식이 참이 되는지를 묻는다.

여 NP-완전 문제들은 NP-완전 문제의 보완 문제로 간주될 수 있다. 여 NP-완전과 NP-완전은 동일한 집합일 수도 있고, 전혀 겹치지 않는 집합일 수도 있다. 후자의 가능성이 더 유력하다고 여겨지지만, 현재로서는 확정된 바는 없다.

관계

여 NP

여 NP는 결정 문제의 복잡도 클래스다. 여기서 문제의 해답이 '아니오'일 때, 그 증명 과정이 다항 시간 내에 검증 가능한 문제들을 포함한다. 다시 말해, 여 NP에 속하는 문제들은 주어진 해답이 틀렸다는 것을 효율적으로 확인할 수 있는 문제들이다.

여 NP-완전 문제는 여 NP 클래스의 문제들 중에서 가장 어려운 문제들을 말한다. 구체적으로, 문제 $C$가 여 NP-완전이 되기 위한 조건은 다음과 같다.

• 문제 $C$가 여 NP에 속해야 한다.
• 모든 여 NP 문제는 문제 $C$로 다항 시간 내에 변환 가능해야 한다.

즉, 여 NP-완전 문제는 여 NP 클래스의 모든 문제를 다항 시간 내에 변환할 수 있는 문제이며, 따라서 여 NP 문제를 해결할 수 있는 다항 시간 알고리즘이 있다면, 여 NP-완전 문제를 해결할 수 있는 알고리즘도 존재한다고 할 수 있다.

NP-완전

• NP-완전(NP-complete) 문제는 NP 클래스의 문제들 중 가장 어려운 문제들이다. NP-완전 문제는 NP 문제를 다항 시간 내에 변환할 수 있는 문제들이다.
• 여 NP-완전 문제와 NP-완전 문제는 서로 보완적인 관계에 있다. 즉, NP-완전 문제의 보완 문제가 여 NP-완전 문제로 간주될 수 있다. 두 클래스가 동일한지, 혹은 전혀 겹치지 않는지는 현재까지 확실하지 않으며, 이는 복잡도 이론의 중요한 미해결 문제 중 하나다.

따라서, 여 NP-완전 문제는 여 NP 클래스에서 가장 어려운 문제들을 나타내며, 이 문제들이 효율적으로 해결될 수 있는 알고리즘이 존재한다면, 모든 여 NP 문제를 효율적으로 해결할 수 있는 가능성이 생긴다.

참고자료

• 〈co-NP-완전〉, 《위키백과》

같이 보기

• NP
• NP-완전
• 여 NP

이 여 NP-완전 문서는 인공지능 기술에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

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