구사과

어떤 decision problem에 대해서, kernel은 그 decision problem의 답을 보존하는 작은 인스턴스다. 그러니까 f : Instance -> Instance인데$|f(x)| \leq g(k)$$Decision(x) = Decision(f(x))$같은 함수가 있으면, decision problem은 $g(k)$ 크기의 kernel이 있다고 함자명한 theorem은, 모든 FPT 문제는 다항시간에 찾을 수 있는 kernel이 존재한다는 것이다.구체적으로 decision problem을 $g(k) n^c$ 에 풀 수 있으면 poly time에 kernel을 찾을 수 있음. 방법은:$n \geq g(k)$ 면, 그냥 $n^{c+1}$에 풀고 trivial yes / no instance..

보호되어 있는 글입니다.

보호되어 있는 글입니다.