NP

NP는 계산 복잡도의 종류 중 하나로, 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합이다. 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이다.

개요

계산 복잡성 이론에서 NP는 의사결정 문제를 분류하는 데 사용되는 복잡성 등급이다. NP는 '예'라는 답이 있는 문제 인스턴스가 결정론적 튜링 기계에 의해 다항 시간 내에 검증 가능한 증거를 갖는 의사결정 문제의 집합이다. 또한 NP의 등가 정의는 비결정론적 튜링 기계가 다항 시간 내에 해결할 수 있는 의사결정 문제의 집합이다. 이 정의는 약어 NP; "nondeterministic, 다항식 시간"의 기본이다. 이 두 가지 정의는 튜링 머신을 기반으로 하는 알고리즘이 두 단계로 구성되는데, 그 중 첫 번째 단계는 비결정론적인 방법으로 생성되는 해법에 대한 추측으로 구성되는 반면, 두 번째 단계는 추측이 문제의 해결책인지를 검증하는 결정론적 알고리즘으로 구성되기 때문에 동등하다. 의사결정 문제는 가장 빨리 알려진 알고리즘에 기초하여 복잡성 등급이 할당된다. 따라서 더 빠른 알고리즘이 발견되면 의사결정 문제가 클래스를 변경할 수 있다. 복합성 등급 P(모든 문제 해결 가능, 결정적으로 다항 시간 내에 해결 가능한 문제)가 NP(다항 시간 내에 해결 가능한 문제)에 포함되어 있음을 쉽게 알 수 있는데, 다항 시간 내에 문제를 해결할 수 있다면 해결책도 문제 해결만으로 다항 시간에서 검증이 가능하기 때문이다. 그러나 NP는 더 많은 문제를 포함하고 있다. 다항식 시간에 그러한 문제를 해결하는 알고리즘도 다항식 시간에 다른 NP 문제를 해결할 수 있다. 또한 복잡도 등급 NP는 NTIME의 관점에서 다음과 같이 정의할 수 있다.

${\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k}).$

여기서 ${\mathsf {NTIME}}(n^{k})$는 비결정론적 튜링 기계가 $O(n^{k})$시간 내에 해결할 수 있는 의사결정 문제의 집합이다. 또는 결정론적 튜링 기계를 검증자로 사용하여 NP를 정의할 수 있다. 공식 언어 'L'은 다항식 'p'와 'q'가 존재하는 경우에만 NP로, 다음과 같은 결정론적 튜링 머신 'M'이 있다.

배경

많은 검색 및 최적화 문제의 의사결정 버전과 같이 많은 컴퓨터 과학 문제가 NP에 포함되어 있다.

검증자 기반 정의

NP의 검증자 기반 정의를 설명하려면 다음과 같은 부분집합 문제를 고려해야 한다. {-7, -3, -2, 5, 8}의 정수를 제공받았다고 가정해 보자. 이 정수의 일부가 0에 해당하는지 알고자 할 때. 정수 {-3, -2, 5}이 (-3) + (-2) + 5 = 0의 합에 해당하므로, 대답은 '예'이다. 합이 0인 부분집합이 존재하는지 여부를 결정하는 작업을 부분집합문제라고 한다. 정수의 일부가 0에 추가되면 응답하기 위해 가능한 모든 하위 집합을 얻는 알고리즘을 만들 수 있다. 알고리즘에 입력하는 정수의 수가 커질수록 하위 집합의 수와 계산 시간은 기하급수적으로 증가한다. 그러나 특정 부분집합이 주어진 경우 부분집합 정수를 합하여 부분집합 합계가 0인지 여부를 효율적으로 확인할 수 있다는 점에 유의해야 한다. 합이 0이면, 그 부분집합은 대답에 대한 증거나 증인이 된다. 주어진 부분집합에 합이 0인지 여부를 검증하는 알고리즘이 검증자이다. 부분 집합의 정수 합계는 다항 시간에 이루어질 수 있으며, 따라서 부분 집합 합 문제는 NP에 있다. 위의 예는 모든 의사결정 문제에 대해 일반화될 수 있다. 문제 $\Pi$ 및 목격자 W의 I가 있을 경우, 순서 쌍(I, W)을 입력으로 지정하도록 검증자 V가 존재한다면, 증인이 다항식 시간에서 답이 "예" 또는 "아니오"라는 것을 증명하면 V는 다항식 시간 내에 "예"를 반환하고 그렇지 않으면 $\Pi$는 NP에 있다.

참고자료

• NP (complexity) Wikipedia - https://en.wikipedia.org/wiki/NP_(complexity)

같이 보기

• 인공지능

이 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 • 딥블루 • 딥페이크 • 멀티모달 • 모달 • 모달리티 • 모달창 • 알렉스넷 • 왓슨 • 텔레파시 • 환각 인공지능 법적 지위 권리주체성 • 전자대리인 • 전자적 인간 • 책임법 • 코파일럿 인공지능 업무 데이터라벨러 • 데이터라벨링 • 크라우드워커 위키 : 자동차, 교통, 지역, 산업, 기업, 단체, 업무, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반