Complexidade computacional: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
→Separações entre outras classes de complexidade: Erro de escrita Etiquetas: Edição via dispositivo móvel Edição feita através do sítio móvel |
|||
Linha 208:
Muitas classes de complexidade conhecidas são suspeitas de não serem iguais, mas isso não foi provado. Por exemplo, '''P''' ⊆ '''NP''' ⊆ '''PP''' ⊆ '''PSPACE''', mas é possível que '''P''' = '''PSPACE'''. Se '''P''' não for igual a '''NP''', então '''P''' não será igual à '''PSPACE''' também. Uma vez que existem muitas classes de complexidade conhecidas entre '''P''' e '''PSPACE''', tais como '''RP''', '''BPP''', '''PP''', '''BQP''', '''MA''', '''PH''', etc, é possível que todas estas classes de complexidade colapsem para uma única classe. Provar que qualquer uma destas classes não são iguais seria um grande avanço na teoria da complexidade.
Na mesma linha, '''co-NP''' é a classe que contém os problemas do complemento (ou seja, problemas com as respostas sim / não
Da mesma forma, não se sabe se '''L''' (o conjunto de todos os problemas que podem ser resolvidos no espaço logarítmico) está contido estritamente em '''P''' ou é igual a '''P'''. Novamente, existem muitas classes de complexidade entre elas, tais como '''NL''' e '''NC''', e não se sabe se elas são classes iguais ou distintas.
| |||