P

  • 다항 시간 내에 해결할 수 있는 문제들.
    • 다항: Polynomial
  • 와 같은 P 복잡도를 가진 문제들이 해당된다.

NP

  • 다항 알고리즘으로는 풀 수 없는 문제들.
    • 비결정적 다항: Nondeterministic Polynomial
    • 다항 시간 내에 해결은 못 하지만, 해결책이 주어졌을 경우 그 해결책이 맞는 해결책인지는 다항 시간 내에 알아낼 수 있다는 특징이 있다.
  • 로는 풀 수 없는 이상의 복잡도를 가진 문제들.
    • 예를 들어 .