P vs. NP vs. NP-hard vs. NP-complete P 다항시간 내에 풀 수 있는 문제 또는 다차시간 알고리즘을 찾은 문제 NP 다항시간 내에 답이 맞았는지 틀렸는지 확인해줄 수 있는 문제 (verification) 또는 다루기 힘들다고 증명되지 않았고, 다차시간 알고리즘도 찾지 못한 문제 NP-hard 아무리 답을 추측해도 그 답이 맞았는지 틀렸는지 확인이 어려운 문제 (예 : 최적화 문제) NP-complete NP-hard임과 동시에 NP인 문제, 즉 모든 NP 문제를 Polynomial-Time Reduction (다항식 시간 변환)시킨 문제가 다시 NP가 될 때, 그 문제를 'NP-complete 문제'라고 부른다. NP-hard NP-hard에 속하는 문제는? 모든 NP-comp..
