DC-UFRPE/Bacharelado em Ciência da Computação/Teoria da Computação/A classe P

Na teoria da complexidade computacional, P é o acrônimo em inglês para Tempo polinomial determinístico (Deterministic Polynomial time) que denota o conjunto de problemas que podem ser resolvidos em tempo polinomial por uma máquina de Turing determinística. Qualquer problema deste conjunto pode ser resolvido por um algoritmo com tempo de execução O(n^{k}), (com k constante).

Podemos ter a classe P como a classe de problemas que são solúveis para um computador real. Embora esta definição não seja exata, é uma boa aproximação para servir de base para nosso estudo.