컴퓨터 과학에서 NP-complete 란 무엇입니까? NP- 완전 문제는 무엇입니까? 컴퓨터 과학에서 왜 그렇게 중요한 주제입니까? NP 는 비 결정적 다항식 시간을 나타냅니다 . 이는 비 결정적 튜링 머신 (일반적인 튜링 머신과 마찬가지로 비 결정적 "선택"기능 포함)을 사용하여 다항식 시간에 문제를 해결할 수 있음을 의미합니다. 기본적으로 솔루션은 폴리 타임 으로 테스트 할 수 있어야 합니다. 이 경우 수정 된 입력으로 주어진 문제를 사용하여 알려진 NP 문제를 해결할 수있는 경우 (NP 문제는 주어진 문제 로 축소 될 수 있음 ) 문제는 NP 완료입니다. NP- 완전 문제에서 벗어나는 가장 중요한 것은 알려진 방법으로 다항식 시간으로 해결할 수 없다는 것입니다. NP-Hard / NP-Complet..