Algorithm/Theory

P(deterministic polynomial time)는 다항시간 내에 답을 구할 수 있는 문제들의 집합. NP는 다항 시간 내에 답을 구할 수 있는 비결정적(Nondeterministric) 알고리즘이 존재하는 decision problem의 집합.(NP : Nondeterministric Polynomially bounded) NP-hard는 모든 NP의 문제들이 polynomial time 내에 문제 H로 환산될 수 있는 문제 H들의 집합.(reducible) NP-complete는 NP에 속하면서, 모든 NP에 대해 polynomial-time내에 reducible한 문제들의 집합.NP-complete에 해당하는 문제는 그들 중 단 한 문제에 대한 효율적인 알고리즘이 존재한다는 것이 증명되면 ..