NP(복잡도)

이 문서에는 일반적인 참조 목록이 포함되어 있지만 대응하는 충분한 인라인 인용이 없습니다. 좀 더 정확한 인용문을 도입하여 개선해 주시기 바랍니다. (2015년 10월) (템플릿 메시지 삭제 방법 및 삭제 시기 확인)

계산 복잡도 이론에서 NP(비결정론적 다항식 시간)는 결정 문제를 분류하는 데 사용되는 복잡도 클래스이다.NP는 "예"인 문제 인스턴스가 결정론적 튜링 기계에 ^{[2][Note 1]}의해 다항식 시간 내에 입증될 수 있는 증거를 가지고 있는 결정 문제의 집합이다.

NP의 동등한 정의는 비결정론적 튜링 기계에 의해 다항식 시간에 해결 가능한 결정 문제의 집합이다.이 정의는 NP의 약어인 "비결정론적, 다항식 시간"의 기초가 된다.튜링 기계에 기반한 알고리즘이 두 단계로 구성되기 때문에 이 두 가지 정의는 동일하며, 첫 번째 단계는 비결정론적 방식으로 생성된 솔루션에 대한 추측으로 구성되고, 두 번째 단계는 추측이 ^[3]문제에 대한 해결책인지 검증하는 결정론적 알고리즘으로 구성됩니다.

복잡도 클래스 P(결정적으로 다항 시간에 해결 가능한 모든 문제)가 NP(다항 시간에 해답을 검증할 수 있는 문제)에 포함되어 있는 것을 쉽게 알 수 있다. 왜냐하면 문제가 다항 시간에 해결 가능한 경우, 간단히 문제를 푸는 것만으로 다항 시간에 해법을 검증할 수 있기 때문이다.그러나 NP에는 더 많은 ^{[Note 2]}문제가 포함되어 있으며, 그 중 가장 어려운 문제는 NP-완전 문제라고 불립니다.다항 시간에 이러한 문제를 푸는 알고리즘은 또한 다항 시간에 다른 NP 문제를 해결할 수 있다.가장 중요한 P 대 NP("P = NP?"") 문제는 NP-완전, 그리고 결과적으로 모든 NP 문제를 해결하기 위한 다항 시간 알고리즘이 존재하는지 여부를 묻습니다.이것은 ^[4]사실이 아니라고 널리 알려져 있다.

복잡도 클래스 NP는 "아니오"라는 답이 다항식 시간에 검증될 수 있는 복잡도 클래스 co-NP와 관련이 있다.NP = co-NP인지 아닌지는 복잡도 ^[5]이론의 또 다른 중요한 질문이다.

형식적 정의

복잡도 클래스 NP는 다음과 같이 NTIME으로 정의할 수 있습니다.

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

${\displaystyle \mathsf{여기}}$서 N ${\displaystyle \mathsf{T}}$ I ${\displaystyle \mathsf{M}}$E ( ${\displaystyle n^{}}$k$)$ ( \ $displaystyle$ \ $mathsf${ $NTIME}}$ ( $n^{k$} )는$$ 비결정론적 튜링 기계로${\displaystyle {}^{}}$ (${\displaystyle {}^{}{n}^{}}$ k$$) \ $displaystyle$O ( $n$^ {$$k )시간$$ $내$에 해결할 수 있는 결정 문제 집합이다.

또는 NP는 결정론적 튜링 기계를 검증자로 사용하여 정의할 수 있다.언어 L은 다항식 p와 q와 결정론적 튜링 기계 M이 존재하는 경우에만 NP에 있다.

• 모든 x 및 y에 대해 기계 M은 입력$({\displaystyle x}$,${\displaystyle y}$)의 시간 p(x )에 실행됩니다.{ displaystyle $(x , y$ ) }
• L의 모든 x에 대해 길이 q(${\displaystyle x)}$의 문자열 y가 존재하며 M ( $x{\displaystyle }$ ,${\displaystyle y}$) $=$ { $displaystyle$ M$(x$,$$y$)=1$}
• L이 아닌 모든 x 및 길이q(x), $M{\displaystyle (x}$ ${\displaystyle ,y}$ ) $=$ { $display style$ M$(x,y$)= $0$} 의 모든 문자열에 대해

배경

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

검증자 기반 정의

NP 의 검증 베이스의 정의를 설명하기 위해서, 서브셋의 합계 문제를 검토합니다.몇 개의 정수 {-7, -3, -2, 5, 8}이 주어졌다고 가정하고, 이 정수들 중 일부는 합계가 0이 되는지 알고 싶습니다.여기서, 정수 {-3, -2, 5}는 (-3) + (-2) + 5 = 0에 해당하므로 대답은 "예"입니다.

몇 개의 정수가 0에 더해진다고 대답하려면 가능한 모든 서브셋을 얻는 알고리즘을 만들 수 있습니다.알고리즘에 입력하는 정수의 수가 증가함에 따라 서브셋의 수와 연산 시간이 기하급수적으로 증가합니다.

그러나 특정 서브셋이 주어지면 서브셋의 정수를 합계함으로써 서브셋의 합이 0인지 여부를 효율적으로 확인할 수 있습니다.합계가 0인 경우, 그 부분 집합은 "예"라는 답변에 대한 증거 또는 증인이 됩니다.특정 서브셋의 합계가0인지 아닌지를 검증하는 알고리즘이 검증자입니다.분명히, 부분 집합의 정수를 다항식 시간으로 합산할 수 있으므로 부분 집합의 합 문제는 NP입니다.

위의 예는 모든 의사결정 문제에 대해 일반화할 수 있습니다.문제$\pi {\displaystyle \mathrm{}}$\$displaystyle \Pi }$의 인스턴스 I와 증인 W가 주어진 경우 순서 쌍(I, W)이 입력으로 지정되도록 검증자 V가 존재하면 증인이 다항 시간에서 "예" 또는 "아니오"라는 답을 증명하면 V는 다항 시간 내에 "예"를 반환하고 그렇지 않으면 $\displaystyle$NPi는$$다항 시간 내에 반환됩니다.

이 문제의 "no" 응답 버전은 "유한 정수 집합이 주어졌을 때, 비어 있지 않은 모든 부분 집합은 0이 아닌 합을 가지고 있는가?"로 명시되어 있다.NP의 검증자 기반 정의에는 "no" 응답자에 대한 효율적인 검증자가 필요하지 않습니다.no-answers에 대한 이러한 검증자의 문제 클래스를 co-NP라고 한다.사실, NP의 모든 문제가 "no-answers"에 대한 검증자를 가지고 있고 따라서 co-NP에 있는지 여부는 미해결 문제이다.

일부 문헌에서는 검증자를 "증명서"라고 하고 증인을 "증명서"^[2]라고 합니다.

기계 정의

검증자 기반 정의와 동등한 특성은 다음과 같습니다. NP는 다항식 시간에 실행되는 비결정적 튜링 기계에 의해 해결 가능한 결정 문제의 클래스입니다.즉, 결정 문제$$${\(\$displaystyle $\Pi)$는 존재 허용 조건을 갖는 다항 시간 비결정적 튜링 $머신{\displaystyle }$M(\$displaystyle$ M$)$에 $의해{\displaystyle \mathrm{}}$ 인식될 때마다 NP에 존재하며, 이는 $(\displaystyle$ w$\in\$pi)의$$ 일부 계산에서 다음과 같은 경우에만 $해당$된다.${\displaystyle M(}$ $)$ {$displaystyle$ M$(w)}$은(는) 수용 상태로 이어집니다.비결정론적 튜링 머신은 비결정론적 방법으로 증명서를 선택하고 증명서에서 검증자를 실행함으로써 다항식 시간에 NP 문제를 해결할 수 있기 때문에 이 정의는 검증자 기반 정의와 동일합니다.마찬가지로, 그러한 기계가 존재한다면, 다항식 시간 검증자는 자연스럽게 그것으로부터 구성될 수 있다.

이러한 관점에서, 우리는 존재 거부 조건을 가진 다항식 시간 비결정론적 튜링 기계에 의해 인식될 수 있는 결정 문제의 클래스로 co-NP를 정의할 수 있다.실존적 거부 조건은 보편적 수용 조건과 정확히 동일하기 때문에, 우리는 NP 대 co-NP 질문을 다항식 시간 비결정적 튜링 기계의 클래스에 대해 실존적 수용 조건과 보편적 수용 조건이 동일한 표현력을 가지고 있는지를 묻는 것으로 이해할 수 있다.

특성.

NP는 결합, 교차, 연결, 클린 별 및 반전 하에서 닫힙니다.NP가 보완 하에 닫혀 있는지 여부는 알려지지 않았다(이 질문은 이른바 "NP 대 co-NP" 질문이다).

일부 NP 문제가 해결하기 어려운 이유

이 클래스의 많은 중요한 문제들 때문에, NP의 문제에 대한 다항 시간 알고리즘을 찾기 위한 광범위한 노력이 있었다.그러나 NP에는 이러한 시도를 거부하는 많은 문제가 남아 있어 초다항 시간이 필요한 것으로 보인다.이러한 문제가 다항식 시간에 결정되지 않는지는 컴퓨터 과학에서 가장 큰 미해결 질문 중 하나입니다(심도 있는 논의는 P 대 NP("P=NP") 문제 참조).

이 맥락에서 중요한 개념은 NP-완전 결정 문제의 집합입니다. NP는 NP의 하위 집합이며 NP에서 "가장 어려운" 문제로 비공식적으로 설명될 수 있습니다. 만약 그것들 중 하나에 다항 시간 알고리즘이 있다면, NP의 모든 문제에 대한 다항 시간 알고리즘이 있고, 이것 때문에 그리고 전용 연구가 있기 때문입니다.h는 어떤 NP-완전 문제에 대한 다항식 알고리즘을 찾는 데 실패했고, 일단 문제가 NP-완전이라는 것이 증명되면, 이것은 이 문제에 대한 다항식 알고리즘이 존재할 가능성이 낮다는 신호로 널리 간주됩니다.

그러나 실제 사용에서는 최적의 솔루션을 찾기 위해 계산 자원을 소비하는 대신 다항식 시간 내에 충분히 좋은(그러나 잠재적으로 차선의) 솔루션이 종종 발견될 수 있습니다.또한 일부 문제의 실제 적용은 이론적인 적용보다 쉽습니다.

정의의 동등성

NP의 두 가지 정의는 비결정론적 튜링 기계(TM)가 다항식 시간에 해결할 수 있는 문제의 종류와 결정론적 튜링 기계가 다항식 시간에 검증할 수 있는 문제의 종류가 같다.그 증거는 많은 교과서, 예를 들어 Sipser의 계산 이론 입문 섹션 7.3에 설명되어 있다.

이것을 나타내기 위해 먼저 결정론적 검증자가 있다고 가정합니다.비결정론적 기계는 단순히 가능한 모든 증명 문자열에 대해 비결정적으로 검증자를 실행할 수 있습니다(각 단계에서 증명 문자열의 다음 문자를 비결정적으로 선택할 수 있고 증명 문자열의 길이는 다항식으로 제한되어야 하기 때문에 이것은 다항식으로 많은 단계를 필요로 합니다).유효한 증명서가 있는 경우, 일부 패스는 받아들여집니다.유효한 증명서가 없는 경우 문자열은 언어로 되어 있지 않으며 거부됩니다.

반대로 A라는 비결정론적 TM이 특정 언어 L을 받아들인다고 가정합니다.다항식적으로 많은 각 단계에서 기계의 계산 트리는 기껏해야 유한한 수의 방향으로 분기합니다.하나 이상의 수락 경로가 있어야 하며, 이 경로를 설명하는 문자열이 검증자에게 제공된 증거입니다.그 후 검증자는 A를 결정적으로 시뮬레이트하여 수용 경로만 추적하고 마지막에 수용하는 것을 검증할 수 있습니다.A가 입력을 거부하면 수락 경로가 없으며 검증자는 항상 거부합니다.

다른 클래스와의 관계

NP에는 모든 문제가 P에 포함되어 있습니다.증거를 무시하고 문제를 해결하는 것만으로 문제의 모든 인스턴스를 확인할 수 있기 때문입니다.NP는 PSPACE에 포함되어 있습니다.이것을 나타내려면 , 모든 프루프 스트링을 루프 해, 각 스트링을 다항 시간 검증기에 공급하는 PSPACE 머신을 구축하는 것으로 충분합니다.다항식 타임머신은 다항식 비트만을 읽을 수 있기 때문에 다항식 공간 이상을 사용할 수도 없고 다항식 공간 이상을 차지하는 증명 문자열을 읽을 수도 없습니다(따라서 우리는 이보다 더 긴 증명을 고려할 필요가 없습니다).NP도 EXPTIME에 포함되어 있습니다.이는 같은 알고리즘이 지수 시간 내에 동작하기 때문입니다.

co-NP는 경우에 따라서는 반례라고 불리는 단순한 증거를 가진 문제를 포함한다.예를 들어, primality testing은 단순히 중요하지 않은 인자를 공급함으로써 정수의 primality를 반박할 수 있기 때문에 3차적으로 co-NP에 있다.NP와 co-NP는 함께 다항식 계층에서 P보다 높은 첫 번째 수준을 형성합니다.

NP는 결정론적 기계만을 사용하여 정의됩니다.검증자가 확률론적(단, 반드시 BPP 기계는^[6] 아니다)인 경우 Arthur에서 Merlin으로 통신하지 않고 Arthur-Merlin 프로토콜을 사용하여 MA 클래스를 해결할 수 있다.

NP는 결정 문제의 클래스이며, 유사한 함수 문제의 클래스는 FNP입니다.

엄밀한 포함은 시간 계층 정리와 공간 계층 정리에서 비롯되며, ${\displaystyle \mathsf{각각}}$ N ${\displaystyle \mathsf{P}}$$$ N X T ${\displaystyle \mathsf{I}}$ ${\displaystyle \mathsf{M}}$ ${\displaystyle \mathsf{E}}$\ $displaystyle \ mathsf$ { $NP$ \ $subsetneq$NEXPTIME$$${\displaystyle \}}$ 및 N $P{\displaystyle \mathsf{}}$ ${\displaystyle \mathsf{e}}$ ${\displaystyle \mathsf{E}}$ ${\displaystyle \mathsf{X}}$ ${\displaystyle \mathsf{P}}$ $display style이다.$

기타 특성화

기술 복잡도 이론의 관점에서, NP는 실존적 2차 논리에 의해 정의될 수 있는 언어들의 집합과 정확히 일치한다.

NP는 매우 단순한 유형의 인터랙티브 증명 시스템으로 볼 수 있으며, 여기서 프로버는 증명서를 제공하고 검증자는 이를 확인하는 결정론적 다항식 타임머신입니다.올바른 증명 문자열이 있으면 받아들일 수 있기 때문에 완성됩니다.허용 가능한 증명 문자열이 없으면 검증자가 받아들일 수 없기 때문에 사운드가 울립니다.

복잡도 이론의 주요 결과는 검증자가 O(log n) 랜덤 비트를 사용하고 증명 문자열의 일정한 비트수(클래스 PCP(log n, 1)만을 조사하는 확률적으로 체크 가능한 증명에 의해 NP가 해결 가능한 문제로 특징지을 수 있다는 것이다.좀 더 비공식적으로, 이것은 위에서 설명한 NP 검증자를 단지 증명 문자열의 몇 곳을 "스팟 체크"하는 것으로 대체할 수 있다는 것을 의미하며, 제한된 동전 던지기 횟수를 사용하면 높은 확률로 정답을 결정할 수 있습니다.이를 통해 근사 알고리즘의 경도에 대한 몇 가지 결과를 입증할 수 있다.

예

NP 에 포함되는 몇개의 문제를 다음에 나타냅니다.

P의 모든 문제, $즉{\displaystyle \mathsf{}\mathsf{P}}$ ${\$ N ${\displaystyle \mathsf{P}}$ \ $displaystyle$\$mathsf { P$ \ $subseteq$ NP$$}$$。P의 문제에 대한 증명서를 부여하면 증명서를 무시하고 다항식 시간 내에 문제를 해결할 수 있습니다.

여행 세일즈맨 문제의 결정 버전은 NP입니다. n개 도시 간의 거리 입력 매트릭스를 통해, 문제는 총 거리가 k 미만인 모든 도시를 방문하는 경로가 있는지 확인하는 것입니다.

증거는 간단히 도시들의 목록이 될 수 있다.그러면 다항식 시간에 명확하게 검증할 수 있습니다.도시 간 경로에 대응하는 매트릭스 엔트리를 추가합니다.

비결정론적 튜링 기계는 다음과 같은 경로를 찾을 수 있습니다.

• 각 도시를 방문할 때마다, 모든 정점을 방문할 때까지, 다음에 방문할 도시를 "추측"할 것입니다.막히면 바로 멈춰요.
• 마지막으로 선택한 루트가 O(n)시간에서 k보다 적은 비용이 들었는지 확인합니다.

사람들은 각각의 추측을 각각의 가능한 경로를 따르기 위해 튜링 기계의 새로운 복사본을 "위킹"하는 것으로 생각할 수 있으며, 만약 적어도 하나의 기계가 k보다 작은 거리의 경로를 발견한다면, 그 기계는 입력을 받아들인다. (동일하게, 이것은 항상 정확하게 추측하는 단일 튜링 기계라고 생각할 수 있다.)

가능한 거리 범위에 대한 바이너리 검색은 반복적으로(다항식 횟수)^[7][8] 결정 버전을 호출함으로써 Traveling Salesman의 결정 버전을 최적화 버전으로 변환할 수 있습니다.

정수 인수분해 문제의 결정 문제 버전: 정수 n과 k가 주어진 경우, 1 < f < k와 f 나눗셈 ^[8]n을 갖는 인수 f가 있습니까?

그래프 G가 그래프 ^[9]H와 동형인 서브그래프를 포함하는지 여부를 결정하는 서브그래프 동형성 문제.

부울 만족도 문제는 부울 변수를 가진 명제 논리학의 특정 공식이 ^[10]변수의 일부 값에 대해 참인지 여부를 알고자 하는 것입니다.

「 」를 참조해 주세요.

• 튜링 머신 – 추상 머신을 정의하는 계산 모델

메모들

레퍼런스

추가 정보

• 토마스 H. 코먼, 찰스 E. 리저슨, 로널드 L. 리베스트, 클리포드 스타인.알고리즘 소개, 제2판MIT Press and McGraw-Hill, 2001.ISBN 0-262-03293-7.섹션 34.2: 다항식 시간 검증, 979–983페이지.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. 섹션 7.3 – 7.5 (NP-완전성, NP-완전성, 추가 NP-완전성 문제), 페이지 241 – 271.
• 데이비드 해럴, 이사이 펠드먼입니다알고리즘:The Spirit of Computing, Addison-Wesley, Reading, MA, 제3판, 2004년.

외부 링크

• 복잡성 동물원: NP
• 전통적이고 최근의 복잡성 이론 연구에 대한 미국 과학자의 입문: "우발적인 알고리즘"