NP 복잡성 이해: 정의 및 예

NP는 "비결정론적 다항식 시간"을 나타냅니다. 문제를 해결하는 데 필요한 시간을 나타내는 복잡성 클래스입니다. NP에서 알고리즘의 실행 시간은 입력 크기에 따라 다항식일 수 있지만 비결정적일 수도 있습니다. 즉, 실행 시간은 알고리즘이 선택한 특정 솔루션에 따라 달라질 수 있습니다. 비결정적 기계에서 다항식 시간 내에 풀 수 있는 문제 종류입니다. 비결정적 기계는 문제에 대해 가능한 모든 솔루션을 병렬로 시도하고 먼저 작동하는 솔루션을 수락할 수 있는 시스템입니다. 이를 통해 기계는 한 번에 하나의 솔루션만 시도할 수 있는 결정론적 기계보다 훨씬 빠르게 일부 문제를 해결할 수 있습니다.

NP 문제의 몇 가지 예는 다음과 같습니다. 각 도시를 정확히 한 번 방문하는 가능한 최단 경로 찾기)
* 배낭 문제(항목 집합과 해당 무게 및 가치가 주어지면 총 가치를 최대화하는 제한된 용량의 배낭에 포함할 항목의 하위 집합 결정)
* 부울 만족성 문제(부울 변수 세트와 해당 제약 조건이 주어지면 모든 제약 조건을 충족하는 변수에 값 할당이 있는지 확인)

NP 복잡도 클래스는 다항식으로 해결하기 어려운 많은 문제를 포함하기 때문에 중요합니다. 시간이 걸리지만 결정론적 기계로 신속하게 확인할 수 있습니다. 이는 알고리즘이 다항식 시간 내에 솔루션을 찾을 수 없더라도 제안된 솔루션을 신속하게 확인할 수 있다면 여전히 유용할 수 있음을 의미합니다.