정확한 알고리즘

Exact algorithm

컴퓨터 과학과 운영 연구에서 정확한 알고리즘은 최적화 문제를 항상 최적성으로 해결하는 알고리즘이다.

P = NP가 아닌 한, NP-하드 최적화 문제에 대한 정확한 알고리즘은 최악의 경우 다항식 시간에 실행할 수 없다.낮은 베이스로 가동 시간이 기하급수적인 정확한 알고리즘을 찾기 위한 광범위한 연구가 있었다.[1][2]

참고 항목

참조

  1. ^ Fomin, Fedor V.; Kaski, Petteri (March 2013), "Exact Exponential Algorithms", Communications of the ACM, 56 (3): 80–88, doi:10.1145/2428556.2428575.
  2. ^ Fomin, Fedor V.; Kratsch, Dieter (2010). Exact Exponential Algorithms. Springer. p. 203. ISBN 978-3-642-16532-0.