'공부' 카테고리의 다른 글
작지도,크지도, 같지도 않다. -1.#IND (0) | 2010.12.29 |
---|---|
언어의 모호성 (0) | 2010.11.16 |
가변인수(va_arg)를 이용한 계산오차 줄이기 (3) | 2010.08.02 |
계산기하 - 원 포함 알고리즘 코딩 (0) | 2010.06.03 |
NP, NP-COMPLETE, NP-HARD (7) | 2010.05.05 |
for문에서 j (3) | 2010.04.26 |
작지도,크지도, 같지도 않다. -1.#IND (0) | 2010.12.29 |
---|---|
언어의 모호성 (0) | 2010.11.16 |
가변인수(va_arg)를 이용한 계산오차 줄이기 (3) | 2010.08.02 |
계산기하 - 원 포함 알고리즘 코딩 (0) | 2010.06.03 |
NP, NP-COMPLETE, NP-HARD (7) | 2010.05.05 |
for문에서 j (3) | 2010.04.26 |
작지도,크지도, 같지도 않다. -1.#IND (0) | 2010.12.29 |
---|---|
언어의 모호성 (0) | 2010.11.16 |
가변인수(va_arg)를 이용한 계산오차 줄이기 (3) | 2010.08.02 |
계산기하 - 원 포함 알고리즘 코딩 (0) | 2010.06.03 |
NP, NP-COMPLETE, NP-HARD (7) | 2010.05.05 |
for문에서 j (3) | 2010.04.26 |
작지도,크지도, 같지도 않다. -1.#IND (0) | 2010.12.29 |
---|---|
언어의 모호성 (0) | 2010.11.16 |
가변인수(va_arg)를 이용한 계산오차 줄이기 (3) | 2010.08.02 |
계산기하 - 원 포함 알고리즘 코딩 (0) | 2010.06.03 |
NP, NP-COMPLETE, NP-HARD (7) | 2010.05.05 |
for문에서 j (3) | 2010.04.26 |
언어의 모호성 (0) | 2010.11.16 |
---|---|
가변인수(va_arg)를 이용한 계산오차 줄이기 (3) | 2010.08.02 |
계산기하 - 원 포함 알고리즘 코딩 (0) | 2010.06.03 |
NP, NP-COMPLETE, NP-HARD (7) | 2010.05.05 |
for문에서 j (3) | 2010.04.26 |
SQL injection on python+SQLite3 (0) | 2010.04.02 |
가변인수(va_arg)를 이용한 계산오차 줄이기 (3) | 2010.08.02 |
---|---|
계산기하 - 원 포함 알고리즘 코딩 (0) | 2010.06.03 |
NP, NP-COMPLETE, NP-HARD (7) | 2010.05.05 |
for문에서 j (3) | 2010.04.26 |
SQL injection on python+SQLite3 (0) | 2010.04.02 |
Google Summer of Code2010 & CGAL (0) | 2010.03.30 |
지나가다가 2013.10.24 17:46 댓글주소 수정/삭제 댓글쓰기
안녕하세요. 지나가다 봤는데, 몇가지 코멘트 남깁니다.
"위에서 예를든 문제 같은 경우에는 NP문제이지만 P문제는 아니다."
무슨 의도인지는 알겠지만 엄밀히 말하면 틀린 문장이네요
NP문제이지만 P문제는 아닐 수도 있다. 라고 표현해야 맞을 것 같네요.
"NP-HARD문제는 정말 어려운 문제로, NP문제가 아니다."
NP-hard 문제는 적어도 하나의 NP-complete problem으로 reduction 되는 문제를 지칭합니다.
보통 어려운 문제들을 지칭할때 이런이런 문제는 NP-complete이다 라는 말을 많이 하는데, 가끔 yes/no question이 아니기 때문에 NP-complete problem 이라는 말을 쓰기 애매한 경우 NP-complete 대신 NP-hard 다 라고 쓰기 때문에 NP-hard가 NP 보다 어려운 문제라는 식의 뉘앙스는 오해의 소지가 있네요.
"사실 P는 NP와 다른것임이 거의 확실해 보인다.
다만 증명이 안되있을뿐이지."
과반수 이상의 학자들이 P가 NP와 다를 것이라고 추정하고 있지만 (기억이 맞다면 60~70%), P=NP라고 믿는 학자들도 많이 있고, 또 현재 우리의 ZFC 공리체계하에서 증명이 불가능한 명제라고 생각하는 분들도 상당수 있습니다.
계산기하 - 원 포함 알고리즘 코딩 (0) | 2010.06.03 |
---|---|
NP, NP-COMPLETE, NP-HARD (7) | 2010.05.05 |
for문에서 j (3) | 2010.04.26 |
SQL injection on python+SQLite3 (0) | 2010.04.02 |
Google Summer of Code2010 & CGAL (0) | 2010.03.30 |
O/R mapping (0) | 2010.02.26 |
NP, NP-COMPLETE, NP-HARD (7) | 2010.05.05 |
---|---|
for문에서 j (3) | 2010.04.26 |
SQL injection on python+SQLite3 (0) | 2010.04.02 |
Google Summer of Code2010 & CGAL (0) | 2010.03.30 |
O/R mapping (0) | 2010.02.26 |
Laplacian Pyramid on GPU (1) | 2010.01.13 |
for문에서 j (3) | 2010.04.26 |
---|---|
SQL injection on python+SQLite3 (0) | 2010.04.02 |
Google Summer of Code2010 & CGAL (0) | 2010.03.30 |
O/R mapping (0) | 2010.02.26 |
Laplacian Pyramid on GPU (1) | 2010.01.13 |
Block-based Web Search (0) | 2009.12.06 |
SQL injection on python+SQLite3 (0) | 2010.04.02 |
---|---|
Google Summer of Code2010 & CGAL (0) | 2010.03.30 |
O/R mapping (0) | 2010.02.26 |
Laplacian Pyramid on GPU (1) | 2010.01.13 |
Block-based Web Search (0) | 2009.12.06 |
오토 레포트 (3) | 2009.11.04 |
Google Summer of Code2010 & CGAL (0) | 2010.03.30 |
---|---|
O/R mapping (0) | 2010.02.26 |
Laplacian Pyramid on GPU (1) | 2010.01.13 |
Block-based Web Search (0) | 2009.12.06 |
오토 레포트 (3) | 2009.11.04 |
Constructive Logic (3) | 2009.09.22 |
댓글을 달아 주세요