- 문제
- 솔루션
- 요약
경우에 당신은에서 시간을 보내 또는 주변의 프로그래밍 커뮤니티을 듣는 용어”P 대 NP”오히려 자주 합니다. 불행히도 공식적인 컴퓨터 과학 교육을받은 많은 사람들조차도 개념에 대한 이해가 약합니다.
그래서 여기에 단순하고 간결한 설명은:
문제
P vs.NP P vs.NP 문제인지 묻는 모든 문제의 해결책이 될 수 있습 빠르게 검증할 수 있습니다 컴퓨터 신속하게 해결하여 컴퓨터가 있습니다., (Wikipedia)
그래서 우리가 P 와 NP 의 의미를 알아 봅시다.
P 문제가 쉽게 해결된 컴퓨터에 의해,그리고 NP 문제는 쉽게 해결할 수 있지만,당신이 현재의 잠재적인 솔루션을 그것의 쉬운지 여부를 확인하고 그것의 올바른 또는하지 않습니다.위의 다이어그램에서 볼 수 있듯이 모든 P 문제는 NP 문제입니다. 즉,컴퓨터가 쉽게 해결할 수 있다면 솔루션을 확인하는 것이 쉽습니다. 그래서 P vs NP 문제는 단지 요청하는 경우 이러한 두 가지 유형의 문제를 동일하거나,서로 다른 경우,즉,거기에 몇 가지 문제는 쉽게 확인하지만 쉽게 해결된다.,
이것은 현재 표시되는 P≠NP,의미를 우리의 많은 예제의 문제는 우리는 빠르게 확인할 수 있습 잠재적인 답변을,하지만 우리는 우리를 해결할 수는 없다. 보자에서 몇 가지 예:
- 외판원이 방문하고자 100 다른 도시를 운전하여,시작하고 끝내는 그의 여행의 집에 있습니다. 그는 제한된 가솔린 공급을 가지고있어서 총 1 만 킬로미터 만 운전할 수 있습니다. 그는 가솔린이 부족하지 않고 모든 도시를 방문 할 수 있는지 알고 싶어합니다., (Wikipedia 에서)
- 농부는 다른 대중의 100 개의 수박을 시장에 가져 가고 싶어합니다. 그녀는 상자에 수박을 포장해야합니다. 각 상자는 깨지 않고 20 킬로그램 만 보관할 수 있습니다. 농부는 10 개의 상자가 그녀가 시장에 100 개의 수박을 모두 가지고 다니기에 충분할 지 알아야합니다. (위)
이러한 문제를 모두 공유 일반적인 특성을 이해하는 데 핵심적인 음모의 대 P NP:를 해결하기 위해서는 그들을 시도해야합니다.이 문제를 해결하려면 어떻게해야합니까?, NP 문제는 사람들에게 너무 흥미 롭습니다. 누구든지 P 가 NP 와 동일하다는 것을 보여줄 수 있었다면 어려운 실제 문제를 컴퓨터에 사소한 것으로 만들 것입니다.
요약
- P vs.NP 상품으로 간의 격차를 수 있는 컴퓨터 신속하게 문제를 해결하는 대 수 있다는 것만으로도 테스트에 대해 제안된 솔루션을 정확성이 있어야 한다.
- 이와 같이,P vs.NP 문제에 대한 검색 방법으로 문제를 해결하기 위해 필요한 노력의 수백만,수십억,또는 수조의 조합에 있는 각 시도하고 하나입니다.,
- 이 문제를 해결하면 컴퓨팅에 지대한 영향을 미치므로 우리 사회에 영향을 미칩니다.
2017 년 2 월 7 일—위키 백과 속성을 추가했습니다.
2014 년 3 월 2 일—혼란을 피하기 위해 설명의 일부를 정리했습니다.