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

인공지능 : 인공지능 서비스, 인공지능 로봇, 인공지능 기술 □■⊕, 인공지능 기업, 인공지능 인물 인공지능 기술 AI 워싱 • 랭체인 • 로봇공학 • 로봇기술 • 인지과학 • 자동추론 • 자연어 처리 • 지능 • 지식표현 • 컴퓨터 비전 • 튜링 테스트 • 프롬프트 • 프롬프트 엔지니어링 문자인식과 음성인식 ICR • OCR • OMR • TTS • URL • 글자 • 답변 • 대화 • 동영상 • 디자인 • 맥락 • 문서 • 문자 • 문자인식 • 문자채팅 • 발음 • 번역 • 분류 • 상담 • 소스코드 • 스토리 • 얼굴 • 얼굴인식 • 음성 • 음성채팅 • 음성인식(STT) • 이미지 • 인공어 • 인공지능 음성 • 자막 • 자연어 • 질문 • 채팅 • 코드 • 코딩 • 텍스트 • 통번역 • 통역 • 파일 • 폴더 • 화상채팅 • 화자인식 인공지능 데이터 데이터라벨러 • 데이터라벨링 • 데이터셋 • 돌마 • 벡터 • 벡터DB • 벡터공간 • 스칼라 • 임베딩 • 크라우드워커 • 토큰 • 토큰화 인공지능 학습 ADP • CoLLM • DALL-E • DDPG • DQN • LAM • LMM • SARSA • sLLM • 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 • 전자대리인 • 전자적 인간 • 책임법 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반