일정 시간의 의사 다항식

Question

의사 다형성은 입력의 크기에 대해 다항식이지만 입력의 크기에 대해 지수 함수임을 의미합니다. 따라서 배낭에서 O (nW)는 의사 다항식으로 간주됩니다. 나는 어떤 사람들이 nx 나 ny라고 부르는 것을 보았습니다. n이 꽤 커지면 n의 비트 길이를 더 고려해야하기 때문에, n을 가진 거의 모든 것, 의사 다항식을 보았습니다. 크기가 다항식으로 간주 될 수있는 변수를 가진 것이 사실은 의사 다항식입니다. 귀하의 의견은 "is the number x a prime number" 같은 단일 번호 인 경우

Answer 1

, 다음 O(x) (또는 O(sqrt(x))는 의사 다항식입니다 - 입력 크기 때문에 입력 크기의 다항식을 의미하지 않는다 x에서 다항식,이 경우 O(logx)입니다

. 그러나 입력이 배열 인 경우 n 요소가있는 경우 입력 길이는 에서 선형이며 O(n)은 다항식을 의미하며 의사 다항식이 아닙니다.