블로그 글 보면서 대충 감 잡으려고 하는데
p 문제는 다항 시간 내로 확실한 하나의 답을 알 수 있는 문제고
np 문제는 다항 시간 내로 답이 있는지 알 수 있는 문제고
np-hard 문제는 다항 시간 내로는 도저히 풀 수 없는 문제라는 거잖아
np-complete는 다항 시간 내로 도저히 풀 수 없지만
답이 있는 지는 알 수 있는 문제라는건가
p 문제
답 - 다항 시간 내로 확인 가능
존재 유무 - 다항 시간 내로 확인 가능
np 문제
답 - 다항 시간 내로 가능한지 불가능한지 모름
존재 유무 - 다항 시간 내로 확인 가능
np-complete
답 - 다항 시간 내로 확인 불가능
존재 유무 - 다항 시간 내로 확인 가능
np-hard
답 - 다항 시간 내로 확인 불가능
존재 유무 - 다항 시간 내로 확인 가능한지 불가능한지 모름
No hard는 다른 모든 np 문제를 다항시간 내에 그 하나의 np hard 문제로 변환할 수 있는걸 말함 Np hard는 그래서 다항시간내에 검증이 될 지 안 될지랑은 무관함 당연히 검증이 가능해서 np hard면서 동시에 np일 수도 있지 그런게 np complete임
그리고 np를 답이 있는지 알 수 있다고 표현할 수 있는지는 잘 모르겠는데 기본적으로는 비결정적 다항시간 알고리즘으로 풀리는게 np고, 여기에 주어진 답이라는 오라클을 둬서 주어진 답을 다항시간 안에 검증할 수 있는 문제를 np라고 표현하는 건 봤음
그러니까 NP라는게 다항 시간 안에는 풀 수 없다는 의미와는 독립적이라는게 요점이고, 동시에 그래서 NP가 P에 속할 수도 있지 않느냐는 추측이 가능한 거임