[일반] P-NP의 의미에 대해서 좀 자세하게 얘기해줄 친구 있니

[속상한기태씨(soksanghae)]

이거 관심도 높은거 알고는 있는데 사실 왜 그렇게까지 중요한지 정확히 이해하고 있지는 못해서 궁금하기도 하네

결과에 대한 추측도 어느 정도 일치하는 거 같던데

[익명(121.166)]

우리가 풀고 싶고 풀면 이론적으로든 실용적으로든 엄청나게 도움이 되지만 NP인 문제가 정말 많음

[익명(121.166)]

ㅇㅇ 예를들면 subgraph isomorphism이라든가 3-SAT이라든가 소인수분해라든가 하나같이 엄청나게 중요한 문제들 특히 NP-complete는 하나 풀리면 나머지도 다 풀수 있으니까 개중요하지 물론 나도 그렇고 대부분 P != NP일걸로 예상하긴 하지만

[익명(77.111)]

정해를 구하는게 NP-hard라면, 근사해를 쉽게 구할수 있다면 practical한 관점에서는 충분한거 아닌가 할 수 있겠지만, 관건은 좋은 근사해조차 쉽게 구할수 없는 경우가 많다. 예를 들어서 최대 크기 clique을 구하는 문제는 NP-hard인데, 그것을 빠르게 효율적으로 근사할 수 있는지에 대한 문제가 있었지. 90년대 후반에 그것이 불가능하다는것이 증명되었고 Acta에 실림.
https://link.springer.com/article/10.1007/BF02392825

[익명(175.204)]

만약 P=NP면 논문 초록에서 NP 문제여서 사실상 못푼다라고 제껴버린 문제들을 전부 재검토해야하는 대격변이 찾아옴 그런 문제들이 한트럭

[익명(222.233)]

P-NP문제를 엄밀하게는 모르지만 일단 조합론적 게임이론 쪽에는 NP-hard인 게임 한 트럭임. CGT붐은 온다..!!

[익명(115.91)]

p=np이면 장난아닐걸