P-NP 문제

1 개요

P versus NP problem

P-NP 문제, P 대 NP 문제

• 복잡도 종류 P와 NP가 같은지에 대한 컴퓨터 과학의 미해결 문제
• 컴퓨터로 풀이법이 빠르게 확인된 문제가 컴퓨터로 빠르게 풀리기도 할 것인가에 관한 문제
• 밀레니엄 문제 중 하나
• P는 NP에 속함. 하지만 NP가 P에 속하는지 여부는 밝혀지지 않음
• 모든 P 문제는 NP 문제임. "NP 문제이면서 P문제가 아닌 것이 존재할까?"
• P=NP인가? P≠NP인가?

 

2 같이 보기

• 밀레니엄 문제
• 게임 복잡도
• 복잡도 P - 결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합
• 복잡도 NP - 비결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합

3 참고

• https://ko.wikipedia.org/wiki/P-NP_문제
• http://navercast.naver.com/contents.nhn?rid=22&contents_id=2260
• http://navercast.naver.com/contents.nhn?rid=22&contents_id=108658