NP

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

개요

계산 복잡성 이론에서 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는 다항식 시간에 실행되는 비결정론적 튜링 기계로 해결할 수 있는 의사결정 문제의 등급이다. 즉, 의사결정 문제 $\Pi$는 $\Pi$가 어떤 다항 시간 비결정론적 튜링 머신 $M$에 의해 '존재적 허용 조건'으로 인식될 때마다 NP에 있으며, 이는 $M(w)$의 일부 계산 경로가 수용 상태로 이어지는 경우에만 $w\in \Pi$임을 의미한다. 비결정론적 튜링 기계는 비결정론적으로 인증서를 선택하고 인증서에 검증기를 실행함으로써 다항 시간 내에 NP 문제를 해결할 수 있기 때문에 이 정의는 검증자 기반 정의와 동등하다. 마찬가지로 그러한 기계가 존재한다면, 다항식 시간 검증기는 그것으로부터 자연스럽게 구성될 수 있다. 이러한 관점에서 공동 NP를 실존적 거부 조건을 가진 다항 시간 비결정론적 튜링 기계가 인식할 수 있는 의사결정 문제의 등급으로 정의할 수 있다. 실존적 거부 조건은 보편적 수용 조건과 정확히 같은 것이기 때문에 실존적 수용 조건과 보편적 수용 조건이 다항 시간 비결정론적 튜링 기계의 등급에 대해 동일한 표현력을 가지고 있는지를 묻는 것으로 NP 대 공동 NP 질문을 이해할 수 있다.

특징

정의의 등가성

다항식 시간에 비결정론적 튜링머신(TM)이 해결할 수 있는 문제 등급으로서의 NP의 두 가지 정의와 다항식 시간에 결정론적 튜링 머신이 검증할 수 있는 문제 등급은 동등하다. 이것을 보여주기 위해 먼저 결정론적 검증기를 가지고 있다고 가정해 보자. 비결정론적 기계는 가능한 모든 증명 문자열에서 비결정론적으로 검증자를 실행할 수 있다. 이것은 각 단계의 증명 문자열에서 비결정적으로 다음 문자를 선택할 수 있기 때문에 다항식적으로 많은 단계만 필요로 하며, 증명 문자열의 길이는 다항식적으로 경계해야 한다. 어떤 증거가 타당하다면 어떤 경로는 수락할 것이고, 증거가 유효하지 않으면 문자열은 언어에 없고 거부될 것이다. 반대로, $A$라는 비결정론적 튜링머신이 주어진 언어 $L$을 받아들인다고 가정하자. 다항식적으로 많은 단계에서 기계의 계산 트리는 최대 한정된 수의 방향으로 분기된다. 적어도 하나의 합격 경로가 있어야 하며, 이 경로를 설명하는 문자열은 검증자에게 제공되는 증명이다. 그런 다음 검증자는 $A$를 결정적으로 시뮬레이션하여 합격 경로만 따르고 마지막에 합격 여부를 검증할 수 있다. $A$가 입력을 거부하면 수용 경로가 없고 검증자는 항상 거부한다.

관계성

NP는 증거를 무시하고 문제를 풀기만 하면 문제의 어떤 인스턴스도 검증할 수 있기 때문에 모든 문제를 P에 담고 있다. 그리고 NP는 PSPACE에 포함되어 있다. 이를 위해 모든 교정 문자열을 루프하고 각 문자열을 다항식 시간 검증기에 공급하는 PSPACE 기계를 제작하기에 충분하다. 다항식 시간 기계는 다항식적으로 많은 비트만 읽을 수 있기 때문에 다항식 공간 이상을 사용할 수 없고, 다항식 공간 이상을 점유하는 교정 문자열을 읽을 수도 없다. 그러므로 이보다 더 긴 증명은 고려하지 않아도 된다. 같은 알고리즘이 지수 시간으로 작동하기 때문에, NP는 EXPTIME에도 포함되어 있다. 여 NP는 어떤 경우를 위한 간단한 증거를 가지고 있지 않고 때로는 반례라고 불리는 문제들을 포함한다. 예를 들어, 소수점 이하 인자를 공급하는 것만으로도 정수의 소수성을 반박할 수 있기 때문에 소수점 이하에서는 소수점 이하인 소수점 이하를 대상으로 한다. NP와 여 NP가 P보다 높은 다항식 계층 구조에서 첫 번째 수준을 형성한다. 또한 NP는 결정론적 기계만을 사용하여 정의된다. 검증자가 확률론적 아서부터 멀린까지의 통신이 없는 아서-머린 프로토콜을 사용하여 클래스 $MA$를 해결할 수 있게 된다. NP는 의사결정 문제의 한 종류이며, 기능 문제의 유사한 종류는 FNP이다. 유일하게 알려진 엄격한 포함은 시간 계층 정리 및 공간 계층 정리에서 나왔으며, 각각 ${\mathsf {NP\subsetneq NEXPTIME}}$ 및 ${\mathsf {NP\subsetneq EXPSPACE}}$이다.

기타 특성화

서술적 복잡성 이론의 측면에서 NP는 실존적 2차 논리(파긴의 정리)에 의해 정의될 수 있는 언어의 집합에 정확하게 대응한다. NP는 매우 단순한 형태의 쌍방향 증명 시스템으로 볼 수 있는데, 검증자는 증명서를 들고 나오고, 검증자는 그것을 확인하는 결정론적 다항식 시간 기계다. 올바른 증빙 문자열이 있으면 받아들이게 되고, 증빙 문자열이 없으면 검증자가 받아들일 수 없기 때문에 건전하기 때문에 완성된다. 복잡성 이론의 주요 결과는 검증자가 $O(log\ n)$ 무작위 비트를 사용하고, 교정 문자열의 일정한 비트 수 $PCP(log\ n,1)$만 검사하는 확률적으로 검사 가능한 증명들에 의해 NP가 해결 가능한 문제로 특징 지어질 수 있다는 것이다. 좀 더 비공식적으로, 이것은 위에서 설명한 NP 검증기를 교정 문자열의 몇 군데를 스폿 점검하는 것으로 교체할 수 있고, 제한된 수의 코인 플립을 사용하면 높은 확률로 정답을 결정할 수 있다는 것을 의미한다. 이를 통해 근사 알고리즘의 경도에 대한 몇 가지 결과가 입증될 수 있다.

참고자료

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

같이 보기

• NP-완전
• 여 NP
• 여 NP-완전

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

인공지능 : 인공지능 서비스, 인공지능 로봇, 인공지능 기술 □■⊕, 인공지능 기업, 인공지능 인물 인공지능 기술 AI 워싱 • 로봇공학 • 로봇기술 • 인지과학 • 자동추론 • 자연어 처리 • 지능 • 지식표현 • 컴퓨터 비전 • 튜링 테스트 • 프롬프트 • 프롬프트 엔지니어링 문자인식과 음성인식 ICR • OCR • OMR • TTS • 답변 • 대화 • 문자 • 문자인식 • 스토리 • 음성 • 음성인식(STT) • 인공어 • 자연어 • 질문 • 화자인식 인공지능 데이터 데이터라벨러 • 데이터라벨링 • 데이터셋 • 크라우드워커 • 토큰 • 토큰화 인공지능 학습 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 • 전자대리인 • 전자적 인간 • 책임법 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반