P vs NP 문제

P vs NP 문제

다항 시간에 해결 가능한 문제(P)와 다항 시간에 검증 가능한 문제(NP)가 같은 클래스인지(P = NP?) 묻는 미해결 수학 문제로, 클레이 수학연구소 밀레니엄 7대 난제 중 하나(상금 100만 달러)

복잡도 클래스 관계

• •P: 다항 시간 해결 가능, 예: 정렬, 최단 경로, MST
• •NP: 다항 시간 검증 가능, P ⊆ NP (확실), P = NP? (미해결)
• •NP-Complete: NP에서 가장 어려운 문제, NP의 모든 문제가 다항 환원 가능, 예: SAT, TSP, 3-색칠
• •NP-Hard: NP만큼 어려우나 NP에 속할 필요 없음(검증 불필요), 예: 정지 문제

관계도: P ⊆ NP, NP-Complete = NP ∩ NP-Hard, P ≠ NP이면 P ∩ NP-Complete = ∅

현재 상태: P ≠ NP가 다수설이나 미증명, P = NP 증명 시 모든 NP-Complete 문제가 다항 시간 해결 가능

의미/영향: 암호학(RSA, 이산로그 기반 암호 무력화 가능), 최적화(물류, 스케줄링 혁신), 인공지능, 수학적 증명

비교: P(빠른 해결) vs NP(빠른 검증) vs NP-Complete(가장 어려운 NP) vs NP-Hard(검증 무관, 최소 NP만큼 어려움)

연관: NP 완전, 환원, SAT, 밀레니엄 문제, 복잡도 이론