P (복잡도)
From Wikipedia, the free encyclopedia
P(PTIME 또는 DTIME(nO(1)))는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이다. 선형 계획 제품, 최대공약수 문제 등이 P에 포함되며, 2002년에는 주어진 숫자가 소수인지 판별하는 문제도 P에 속한다는 것이 증명되었다[1]
보통 P는 효율적으로 다룰 수 있는 문제의 집합으로 생각되지만, RP나 BPP와 같은 더 큰 집합의 문제도 효율적으로 다룰 수 있다. 또한 P에 속한다고 해서 항상 실용적인 것은 아닌데, 이론적으로는 다항 시간 내에 풀 수 있지만 실제 걸리는 시간이 비효율적일 가능성도 충분히 있기 때문이다.