컴게에 물어보려다 아무래도 수학/과학에도 포함되는거같아 과게로 왔어요
P는 다항시간안에 해결가능한 문제이고(solved)
NP는 다항시간안에 판별가능(verified)
NP-Complete는 만약 NP-Complete라는 문제 X가 있을때
X는 NP이고 NP에 속하는 문제를 X로 다항시간안에 변환이 가능하면 X를 NP-Complete이라고 말하는것이죠?
그럼 NP-Complete를 다항시간안에 풀면
P = NP라는 엄청난 결과가 나오는거 맞죠?
그럼 NP-Complete도 결국 NP이라는건데(제가 이해하기엔)
그럼 NP-Complete도 어떠한 입력에 다항시간안에 예/아니오를 답변하는게 가능한거죠?
다만 풀어내는 해답(알고리즘)이 없어서 못푸는거죠?
제가 이해한게 맞나요?
인터넷 자료 모아서 제머리로 이해하기가 확실치 않네요
글쓰기