classe de complexidade

Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas relacionados aos recursos computacionais baseados em complexidade. Uma típica classe de complexidade é definida da seguinte forma: O conjunto de problemas que podem ser resolvidos por uma máquina abstrata M usando O(f(n)) de recurso R, onde n é o tamanho da entrada. Por exemplo, a classe NP é o conjunto de problemas decidíveis que podem ser resolvidos por uma Máquina de Turing Não-Determinística em tempo polinomial, onde a classe PSPACE é o conjunto de problemas decidíveis que podem ser resolvidos por uma Máquina de Turing Determinística em espaço polinomial. As mais simples classes de complexidade são definidas pelos seguintes fatores: * O tipo de problema computacional: os mais comumentes usados são o problemas de decisão. Contudo, classes de complexidade podem ser definidas baseadas nos problemas funcionais (Um exemplo é o conjunto FP), problemas de contagem (Ex. #P), problemas de otimização, problemas de promessa, etc. * O modelo de computação: o modelo de computação mais comum é a Máquina de Turing Determinística, porém, muitas classes de complexidade são baseadas em Máquinas de Turing Não-Determiníticas, circuitos booleanos, Máquina de Turing Quântica, circuitos monótonos, etc. * O(s) recurso(s) que está(ão) sendo limitado(os) e os limites: Estas duas propriedades são usualmente declaradas juntas, assim como "tempo polinomial", "espaço logarítmico", "constante de profundidade", etc. Muitas classes de complexidade podem ser caracterizadas em termos da matemática lógica, necessária para expressá-las. Delimitar o tempo computacional por cima por alguma função concreta f(n) muitas vezes produz classes de complexidade que dependem da escolha do modelo da máquina. Por exemplo, a linguagem {xx| x é uma cadeia binária} pode ser decidida em tempo linear numa Máquina de Turing Multi-Fita, mas necessariamente requer um tempo exponencial no modelo da Máquina de Turing de fita simples. Se nós permitirmos um variação polinomial em tempo de execução, a tese de Cobham-Edmonds afirma que, "as complexidades de tempo em dois modelos razoáveis e gerais são polinomialmente relacionados" (Goldreich 2008, Capítulo 1.2). Esti forma a base da classe de complexidade P, a qual é o conjunto de problemas resolvidos por uma Máquina de Turing Determinística dentro de um tempo polinomial. O conjunto correspondente de problemas funcionais para P é FP. Os axiomas de Blum podem ser usados para definir classes de complexidade sem se referir a um modelo computacional concreto.