O que é a classe de complexidade

12

O que significa a classe de complexidade ? Eu sei que é a classe de complexidade que contém as linguagens para as quais existe uma máquina de Turing não determinística no tempo polinomial, de modo que se o número de estados de aceitação da máquina na entrada for ímpar.PPPAMxAMx

Mas o que significa ? Eu simplesmente não consigo seguir o que realmente faz :)PP

Quais são as consequências práticas dessa classe de complexidade e como é possível mostrar que ?PP=P

Stewenson
fonte
2
Essa notação (estranha) denota classes de complexidade relativa ou oráculo. Veja Wikipedia para uma definição. Isso responde a pergunta? Caso contrário, edite para esclarecer.
Raphael
7
Você vai encontrar a prova de em cs.rutgers.edu/~allender/538/murata3.pdfPP=P
sdcvvc

Respostas:

11

PP denota a classe equipada com o que é conhecido como oráculo para - dizemos que foi dada a capacidade de determinar se uma string é ou não membro de uma linguagem contido na classe em uma única operação.PPsLP

Vejo que outro comentarista (sdcwc) se vinculou à prova de (veja essas notas em uma palestra do CS 538 em Rutgers ). Uma classe de complexidade que é uma técnica para uma classe de tal modo que , é dito para ser baixa para a classe . Nesse caso, dizemos que é baixo para si.PP=PCBBC=BBP

Josh Lockhart
fonte
Outro link para você, desta vez para a página da wikipedia sobre 'baixa' de classes de complexidade: en.wikipedia.org/wiki/Low_%28complexity%29
Josh Lockhart
Seu estilo de explicação é suficiente para a compreensão dos princípios básicos e é fácil de seguir.
27512 Stephenson
O que você quer dizer com basicamente que está equipado com o oráculo que pode determinar a associação da língua L no único passo? Do meu ponto de vista, se você está resolvendo algum problema em P P , está consultando o oráculo no início do cálculo, portanto, após o primeiro passo, você sabe como o oráculo responde a você? Então você sabe que desde que atingiu um estado de aceitação, o número de tais estados é apenas um, então o número ímpar, então você aceita? PLPP
27412 Jan
3
"um oráculo para - dizemos que foi possível determinar se uma língua L é ou não membro de P em uma única operação." - isso é incorreto: Um oráculo dá a capacidade de determinar se uma string s é membro de alguma linguagem L em P . Sem perda de generalidade, L pode ser feita para ser S A T (uma vez que é P -completo)PLPsLPLSATP
sdcvvc
Estou tentando seguir a prova muito difícil, mas não está claro para mim. Por exemplo, o que significa a função ? Eu sei que é "repita 1 i vezes ( 1 3 = 111 )", mas o que é bom nesse contexto? O que especialmente 1 i significa? E o k em n k em todos os lugares? Se i n k , então f ( 1 i , x ) = f ( 1 n k , x )f(1i,x)13=1111iknkink . O que isso significa? Por que você tem uma função f P com essa entrada? f(1i,x)=f(1nk,x)=f(1|x|k,x)fP
27412 Jan