🚀궤도사령부(궤도)

np문제는 지수시간으로만 풀이가 가능한가요?

질문

인사할시간도없

23.03.21

알고리즘 문제를 풀다가, 시간 복잡도가 O(4^N)이 걸리는 문제를 만났는데

그 문제가 np문제라서 BFS를 써도 선형 시간 안에는 못푼다고 했는데

NP문제가 오직 지수시간 만으로 풀수 있나요?

동적 계획법을 하면 NlgN 같은 시간도 나올거 같은데..

슈윙거팬티도둑파인만

23.03.21

이 글을 읽는 저희가 그게 무슨 문제인지를 모르는데 p로 가능하다는 사실을 주장한다면 밀레니엄 문제를 풀었다는 얘기가 아닐련지..

제발스마트포인터써줘

23.03.22

제가 같은 말을 적으려고 했는데 이미 댓글에 있었네요 ㅎㅎ...

궤소리방정식

23.03.22

NP집합이 EXP집합에 포함되기 때문에 모든 NP문제는 아무리 많이 걸려도 지수시간 안에는 풀 수 있음이 증명되어 있습니다. 근데 더 빠르게 풀리는 방법이 존재할지도 모르죠. 만약 횐님께서 어떤 NP문제를 항상 지수시간보다 적게 (n lg n 이라던지) 풀 수 있음을 증명하신다면 횐님은 그 문제에 대한 깊은 이해를 발견해서 브루트포스보다 훨씬 효율적인 방법을 찾아내신 겁니다. 그러면 그 문제는 NP가 아니라 P가 되겠죠. 만약 그 문제가 NP-완전 이였다면 P-NP문제를 푸신거고요.

궤소리방정식

23.03.22

조건을 좀 다르게 하면 다항식 시간 안에도 풀 수 있어요. 확률을 좀 섞어서 알고리즘이 90%로 다항식 시간안에 풀어진다던지, 이론적으로는 NP지만 실전에선 대부분 다항식 시간안에 풀어진다던지 (SAT이라는 문제가 이에 해당됩니다)

인사할시간도없 글쓴이

23.03.22

다시 한번 찾아봤는데 NP문제가 P-NP난제의 NP에서 나온걸 이제야 알아서 당연한 소리를 질문한거 같아서 부끄럽네요..

@궤소리방정식

궤소리방정식

23.03.22

아녜요! 과거에는 NP인줄 알았는데 P로 밝혀진 문제들도 많습니다. 되게 신기한 사실이지요.

@인사할시간도없

궤도