-
P and NP (P NP 문제)알고리즘 2020. 12. 13. 00:57
P문제란?
다항시간 내(reasonable time)에 답을 구할 수 있다.
다루기 쉬운 문제
결정론적 다항시간 문제
NP문제란?
Nondeterministic Plynomial time
다항시간 내 풀 수 없는 문제
다항시간내에 풀 수 있는지 없는지 모른다.
다루기 어려운 문제
비결정론적 다항시간 문제 -> 적어도 검산은 쉽게 할 수 있는 문제. 하지만 답을 찾기는 어려운 문제
Unsolvable problems
어떤 알고리즘으로도 풀 수 없는문제
Optimization/Decision problems
Hamiltonian paths and cycles
Traveling salesman problem
Is P=NP?
P⊆NP
P=NP라면? 복잡하고 어려운 문제들을 다항시간 내에 반드시 풀 수 있다. 하지만 NP를 P로 바꾸는 알고리즘이 존재한다는 것만을 알게되는 것이고 그 알고리즘을 찾는 일은 어려울 수 있다.
P=NP가 증명되면 알고리즘을 찾는 일은 어렵다 하더라도 찾으려는 노력이 의미있는 일이 된다.
P≠NP라면?
찾으려고 노력할 필요가 없다.
'알고리즘' 카테고리의 다른 글
[동적계획법/Dynamic Programming]LCS 문제(최장 공통 부분 수열) 파이썬 코드 (0) 2020.12.20 Shortest Path Problem(최단거리 문제) (0) 2020.12.13 Minimum SpanningTree(최소 비용 신장 트리) (0) 2020.12.13 Greedy Algorithm(그리디 알고리즘) (0) 2020.12.13 Dynamic Programming (동적 계획법) (0) 2020.12.13