24b0d121e09c28a8699fe8b115ef046c62f82b4f9d

너 다항시간의 정의 모름??


여기서 다항시간은 유한한 시간 같은 걸 말하는 게 아니라,


어떤 k에 대하여 O(n^k)의 시간복잡도를 말하는 건데?


주어진 결정문제에 대해, ∃k T_A(n) = O(n^k)를 만족하는 알고리즘 A가 존재해야 된다고.


그러니까 x ∈ P라는 건,


결정 문제 x에 대해서 어떤 알고리즘이 존재해서 다항시간 복잡도로 풀 수 있다는 걸 말하는 거야.


예를들어 n개의 숫자 중에 짝수가 존재하냐는 결정 문제는,

for i <- 1 to n
    if arr[i]를 2로 나눈 나머지가 0 then,
        return Yes


return No


처럼 알고리즘 짜면 n번만 나누면 되니까 O(n)의 시간 복잡도로 풀 수 있어서 P 문제가 되는 거고.


애초에 O(n^n!)이나 O(n↑↑n) 같은 괴랄한 시간복잡도도 유한한 건 마찬가지인데 어떻게 다항시간을 '유한한 시간'이랑 동치로 보는 거임??

내가 컴공이라 물리학은 잘 몰라서 이전에 너가 쓴 이론이 얼마나 허술한지 몰랐는데 다항시간도 모르는 거 보니까 걍 역대급으로 허술한 거였네.


리만가설 증명했다는 잼민이들이랑 다를 게 없었노...