NP는 Nondeterminisitic Polynomial-time의 약자로, NP-complete problem은 효율적인 해결 알고리즘이 현재까지 알려지지 않은 계산 문제 중의 하나다. 많은 중대한 컴퓨터 싸이언스 문제들이 이 종류에 속하는데 여기엔 Knapsack problem(배낭 문제), The traveling salesman problem(외판원 문제), Boolean satisfiability problems(충족 가능성 문제)와 Graph coloring problems(그래프 색칠 문제) 등이 있다.
계산 복잡성 이론에 따르면, 다음의 두 조건을 만족할 경우 NP-complete problem이다:
1. 각 해법의 정확함이 빠른 시간 안에 확인이 되고, 모든 가능성 있는 해법을 시도하는 무작위 탐지 알고리즘을 통해 해법을 찾을 수 있는 문제 일 때
2. 해당 문제가 빠른 시간에 확인이 가능한 모든 다른 문제에 대해 시뮬레이션이 가능하고 그것이 정답일 수 있다. 이러한 의미에서 빠르게 확인이 가능한 해법들을 갖고있는 문제들 중의 가장 어려운 문제다. 따라서 우리가 어떤 NP-Complete problem에 대해 빠르게 해법을 찾을 수 있다면, 우리는 다른 모든 문제에 대해서도 빠르게 해법(단, 이 해법은 쉽게 확인이 가능해야한다.)을 찾을 수 있다.
NP-complete problem, any of a class of computational problems for which no efficient solution algorithm has been found. Many significant computer-science problems belong to this class—e.g., the traveling salesman problem, satisfiability problems, and graph-covering problems.
In computational complexity theory, a problem is NP-complete when:
1. it is a problem for which the correctness of each solution can be verified quickly and a brute-force search algorithm can actually find a solution by trying all possible solutions.
2. the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense it is the hardest of the problems to which solutions can be verified quickly so that if we could actually find solutions of some NP-Complete problem quickly, we could quickly find the solutions of every other problem to which a solution once given is easy to check.
출처
'기술(Tech, IT) > etc.' 카테고리의 다른 글
| [Tech, etc] Python vs Python3 (0) | 2022.06.13 |
|---|---|
| [Tech, etc] Primitive recursive function(원시 재귀 함수) (0) | 2022.05.04 |
| [Tech, etc.] Ackermann function(아커만 함수) (0) | 2022.05.03 |
| [Tech, etc.] Architectural smell (0) | 2021.09.21 |
| [etc.] Platform-based design (0) | 2021.09.12 |