[질문] NP 완전문제가 다항시간내에 해결이 가능한 어떤 문제인거임?

[익명(222.236)]

그중 제일 어려운 것을 이야기하는거고?

한두마디로 딱 정의를 내려보고 싶은데 알듯 말듯 하면서도 헷갈리네

[익명(222.233)]

NP: 비결정론적 튜링머신을 다항시간에 해결 가능 / NP-Hard: 모든 NP 문제를 A로 환원시킬 수 있을 때 A는 NP-Hard / NP-Complete: NP-Hard이면서 NP인 문제 - dc App

[익명(49.142)]

"다항시간내에 해결이 가능한 어떤 문제" 는 P

[익명(121.125)]

NP완비중에 하나라도 다항시간에 풀면 P=NP증명한거임