NP는 다항식 시간 검증 기능을 갖춘 언어 클래스입니다.

/ / 에 게시됨 사이버 보안, EITC/IS/CCTF 계산 복잡도 이론 기초, 복잡성, NP 및 다항식 검증 가능성의 정의

"비결정론적 다항식 시간"을 의미하는 클래스 NP는 이론 컴퓨터 과학의 하위 분야인 계산 복잡성 이론의 기본 개념입니다. NP를 이해하려면 먼저 예 또는 아니오로 대답할 수 있는 질문인 의사결정 문제의 개념을 이해해야 합니다. 이 맥락에서 언어는 일부 알파벳에 대한 문자열 집합을 나타내며, 각 문자열은 결정 문제의 인스턴스를 인코딩합니다.

(L)에 대한 다항식 시간 검증자가 있으면 언어(L)가 NP에 있다고 말합니다. 검증자는 인스턴스(x)와 인증서(y)라는 두 가지 입력을 취하는 결정적 알고리즘(V)입니다. 증명서(y)는 "증인" 또는 "증거"라고도 합니다. 검증자(V)는 인증서(y)가 (x)가 언어(L)에 속함을 확인하는지 확인합니다. 공식적으로 모든 문자열(x in L)에 대해 다음을 포함하는 문자열(y)이 존재하는 다항식 시간 알고리즘(V)과 다항식(p(n))이 있으면 언어(L)는 NP입니다. |y| leq p(|x|)) 및 (V(x, y) = 1). 반대로, 모든 문자열(L이 아닌 x)에 대해 (V(x, y) = 1)과 같은 문자열(y)은 없습니다.

이 개념을 설명하기 위해 잘 알려진 "부울 만족성"(SAT) 문제를 고려하십시오. SAT 문제는 주어진 부울 공식의 변수에 진리값을 할당하여 해당 공식이 참으로 평가되는지 여부를 묻습니다. SAT 문제는 부울 공식(phi)과 변수에 대한 진리값 할당(alpha)이 주어지면 (alpha)가 (phi)를 만족하는지 다항식 시간에 확인할 수 있기 때문에 NP에 있습니다. 여기서 인스턴스( x )는 부울 공식( phi )이고 인증서( y )는 할당( alpha )입니다. 검증자(V)는 (alpha)가 (phi)를 참으로 만드는지 확인하는데, 이는 (phi)의 크기에 대해 다항식 시간 내에 수행될 수 있습니다.

또 다른 예시는 "해밀턴 경로(Hamiltonian Path)" 문제입니다. 이 문제는 주어진 그래프에서 각 정점을 정확히 한 번만 방문하는 경로가 있는지 묻습니다. 해밀턴 경로 문제는 그래프( G )와 정점 시퀀스( P )가 주어지면 ( P )가 ( G )에서 해밀턴 경로인지 다항식 시간으로 확인할 수 있기 때문에 NP에도 있습니다. 이 경우 인스턴스( x )는 그래프( G )이고 인증서( y )는 정점 시퀀스( P )입니다. 검증자(V)는 (P)가 해밀턴 경로를 형성하는지 여부를 확인하며, 이는 (G)의 크기에 대해 다항식 시간에 수행될 수 있습니다.

다항식 시간 검증 가능성의 개념은 솔루션을 찾는 것이 계산적으로 불가능할지라도 효율적으로 검사할 수 있는 문제를 특성화하는 방법을 제공하기 때문에 중요합니다.이것은 ( P = NP )라는 유명한 질문으로 이어집니다.이 질문은 다항식 시간 내에 솔루션을 검증할 수 있는 모든 문제가 다항식 시간 내에 해결될 수 있는지 여부를 묻습니다.클래스 ( P )는 결정적 튜링 머신으로 다항식 시간 내에 해결할 수 있는 결정 문제로 구성됩니다.만약 ( P = NP )이면 다항식 시간 검증자가 있는 모든 문제에는 다항식 시간 솔버도 있다는 것을 의미합니다.이 질문은 컴퓨터 과학에서 가장 중요한 미해결 문제 중 하나로 남아 있습니다.

NP의 주요 특성 중 하나는 다항식 시간 단축 하에서 닫혀 있다는 것입니다. 언어( L_1 )에서 언어( L_2 )로의 다항식 시간 단축은 ( x in L_1 ) 경우에만 ( f(x) in L_2 )인 다항식 시간 계산 함수( f )입니다. ( L_1 )에서 ( L_2 )로의 다항식 시간 감소가 존재하고 ( L_2 )가 NP에 있는 경우 ( L_1 )도 NP에 있습니다. 이 속성은 NP의 "가장 어려운" 문제를 식별하는 NP-완전성 연구에 중요한 역할을 합니다. NP에 있는 문제는 NP-완전이며 NP의 모든 문제는 다항식 시간 내에 해당 문제로 축소될 수 있습니다. SAT 문제는 NP-완전성이 입증된 최초의 문제였으며, 다른 문제의 NP-완전성을 증명하는 기초가 됩니다.

다항식 시간 검증 가능성의 개념을 더 자세히 설명하려면 "부분 집합 합계" 문제를 고려하세요. 이 문제는 지정된 목표 값을 합산하는 주어진 정수 집합의 하위 집합이 존재하는지 묻습니다. 부분 집합 합 문제는 정수 집합( S ), 목표 값( t ) 및 ( S )의 부분 집합( S' )이 주어지면 다항식 시간에 요소의 합이 다음과 같은지 확인할 수 있기 때문에 NP에 있습니다. ( S' )는 ( t )와 같습니다. 여기서 인스턴스( x )는 쌍( (S, t) )이고 인증서( y )는 하위 집합( S' )입니다. 검증기(V)는 (S')에 있는 요소의 합이 (t)와 같은지 확인합니다. 이는 (S)의 크기에 대해 다항식 시간 내에 수행될 수 있습니다.

다항식 시간 검증 가능성의 중요성은 이론적 고려 사항을 넘어선다. 실제적인 측면에서, 이는 NP 문제의 경우 제안된 솔루션(인증서)이 제공되면 효율적으로 확인할 수 있다는 것을 의미한다. 이는 암호화 프로토콜, 최적화 문제 및 솔루션의 정확성을 검증하는 것이 중요한 다양한 분야에 상당한 영향을 미친다.

요약하자면, 클래스 NP는 제안된 솔루션이 결정론적 알고리즘에 의해 다항식 시간 내에 검증될 수 있는 결정 문제를 포함합니다. 이 개념은 계산 복잡성 이론의 기초가 되며 컴퓨터 과학의 이론적 측면과 실제 측면 모두에 심오한 영향을 미칩니다. NP, 다항식 시간 검증 가능성 및 NP-완전성과 같은 관련 개념에 대한 연구는 계속해서 활발하고 중요한 연구 분야입니다.

기타 최근 질문 및 답변 복잡성:

복잡성에서 더 많은 질문과 답변 보기

더 많은 질문과 답변:

아래의 태그 : , , , , ,