| 파일 유형 | APK |
|---|---|
| 버전 | 3.2.2 |
| 발행자 | Ofek Ron |
| 출시일 | 2020. 8. 20. |
| 추가 된 날짜 | 2020. 8. 20. |
| OS 요구 사항 | Android |
| 요구 사항 | Requires Android 4.1 and up |
| 총 다운로드 | 0 |
| 가격 | Free |
기술
P 대 NP 문제는 컴퓨터 과학의 주요 미해결 문제입니다. 컴퓨터로 신속하게 솔루션을 확인할 수 있는 모든 문제가 컴퓨터로도 신속하게 해결할 수 있는지 여부에 대해 설명합니다. 첫 번째 정답에 대해 미화 1,000,000달러의 상금을 수여하기 위해 Clay Mathematics Institute에서 선정한 7개의 Millennium Prize 문제 중 하나입니다. 해밀턴 순환 문제는 그래프 이론 분야에서 잘 알려진 NP-완전 문제입니다. 예를 들어 주어진 입력에서 이를 해결하는 다항식 알고리즘을 찾는 것과 같은 문제를 해결하면 인류가 P 대 NP 문제를 해결하는 데 어느 때보다 가까워질 것입니다.
이 게임에서는 노드와 에지의 집합인 그래프가 제공되며, 여기에는 때때로 해밀턴 주기(자세한 내용은 여기 https://en.wikipedia.org/wiki/Hamiltonian_path_problem에서 자세히 알아보기)를 포함하고 때로는 포함하지 않습니다. 해밀턴 주기를 노출하거나 해당 그래프에 대해 존재하지 않는다고 결정하여 해결해야 합니다.
그래프가 해밀턴인지 결정하기 위한 큰 팁(해밀턴 주기 포함)은 https://en.wikipedia.org/wiki/Graph_toughness에서 찾을 수 있습니다.
100만 달러 문제를 풀고 그래프 이론을 배워보세요!
