P-NP문제와 NP-Hard
2020. 4. 14. 15:16ㆍ통계 빠개기/Statistics
https://eehoeskrap.tistory.com/286
P문제와 NP문제(NP-hard)
답이 YES 아니면 NO로 반환되는 문제를 결정 문제라고 한다. 예를 들어, 'a는 b의 배수인가?'와 같은 질문은 결정 문제이다. P와 NP 모두 결정 문제의 분류에 해당한다. P 문제는 결정 문제들 중에서 쉽게 풀리는..
eehoeskrap.tistory.com
https://ko.wikipedia.org/wiki/NP-%EB%82%9C%ED%95%B4
NP-난해 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. NP-난해, NP-hard는 NP에 속하는 모든 판정 문제를 다항 시간에 다대일 환산할 수 있는 문제들의 집합이다. 다시 말하면, NP-난해는 적어도 모든 NP 문제만큼은 어려운 문제들의 집합이다. NP-난해 집합에 속하는 문제가 NP에도 속하면 NP-완전에 속한다. 즉, NP-완전은 NP와 NP-난해의 교집합이다. 만약 P-NP 문제가 P=NP로 풀린다면 P=NP=NP-완전이므로 P와 NP는 NP-난해의 부분집합이 되고
ko.wikipedia.org
'통계 빠개기 > Statistics' 카테고리의 다른 글
| [Proof] Normal Equation (0) | 2020.04.17 |
|---|---|
| [Overview] OLS, Normal Equation, Gradient Descent (0) | 2020.04.17 |
| [Overview] Co-variance Corr (Formula) (0) | 2020.04.17 |
| soft argmax에 관한 의문점 (0) | 2020.04.12 |
| Cross-Entropy에 관한 의문점 (0) | 2020.04.12 |