NP-problem

지각생 연습장
  • NP Problem이란? : 근성공돌이의 주저리
    • 'NP-Hard'라고 불리는 문제들은 세일즈맨의 여행 문제처럼 모든 경우의 수를 전부 확인해보는 방법 이외에는 정확한 답을 구할 수 있는 뾰족한 수가(즉, 적당한 알고리즘이 존재하지 않는) 없는 문제들을 뜻한다.
    • 어떤 문제가 NP에 속함과 동시에 NP-Hard에 속한다면, 우리는 그것을 'NPC(NP-Complete) 문제'라고 부른다.
    • 컴퓨터 학자들과 프로그래머들은 대개 NP 완전 문제를 실용적인 관점에서 해결하기 위해서 진짜 정답을 찾는것을 포기하고 훨씬 적은 양의 계산을 통해서 정답에 가까운 값을 찾는 것으로 만족한다. 이러한 알고리즘은 근사 알고리즘(approximation algoritm) 혹은 발견적 알고리즘(heuristic algoritm)이라고 부른다. MST, 탐욕적 알고리즘, 평면 절단 방법 등은 모두 이러한 알고리즘의 예인데, 실전 프로그래밍의 세계에서는 이러한 근사 알고리즘이 생각보다 많이 사용된다.
    • 'NP Problems' = 'P Problem' U 'NP complete'
  • 수학7대난제
개인 도구