Classes de complexidade semântica versus sintática

35

Em seu livro "Computational Complexity", Papadimitriou escreve:

RP é, de certo modo, um tipo novo e incomum de classe de complexidade. Nenhuma máquina de Turing não determinística polinomialmente limitada pode ser a base para definir uma linguagem em RP. Para que uma máquina N defina uma linguagem em RP , ela deve ter a propriedade notável de que em todas as entradas ela rejeita por unanimidade ou aceita por maioria . A maioria das máquinas não determinísticas se comporta de outras maneiras por pelo menos algumas entradas ... Não há uma maneira fácil de saber se uma máquina sempre pára com uma saída certificada. Chamamos informalmente essas classes de classes semânticas , em oposição às classes sintáticas , como P e NP, onde podemos verificar imediatamente, através de uma verificação superficial, se uma máquina adequadamente padronizada realmente define um idioma na classe.

Várias páginas depois, ele aponta que:

a linguagem L está na classe PP se houver uma máquina de Turing N polinomialmente não determinística, tal que, para todas as entradas x, se mais da metade dos cálculos de N na entrada x acabarem aceitando. Dizemos que N decide L por maioria .xL

Pergunta 1: Por que Papadimitriou conclui que o PP é uma classe sintática, enquanto sua definição é apenas ligeiramente diferente da de RP ?

Pergunta 2: Se ser "semântico" para uma classe de complexidade equivale a NÃO ter problemas completos, ou a falta de problemas completos é considerada uma propriedade que adivinhamos que as classes semânticas possuem?

Editar: consulte o tópico relacionado Todas as classes de complexidade têm uma caracterização de idioma da folha?

MS Dousti
fonte
2
uma palestra relacionada recente Anuj Davar pelo INI: Em classes de complexidade sintática e semântica
Kaveh
@ Kaveh: Muito obrigado! Vou dar uma olhada nisso.
MS Dousti

Respostas:

31

O RP envolve uma promessa de que 0 caminhos aceitam ou mais da metade aceitam, não importa qual seja a entrada. Para PP, não existe tal promessa. Se mais de metade dos caminhos aceitar, então , de outro modo, . (O PP pode ser definido para que os critérios de aceitação sejam e respectivamente.)x L 1 / 2 < 1 / 2xLxL1/2<1/2

Ou, em outras palavras, se eu fornecer uma TM probabilística afirmando que é uma máquina de PP que decide algum idioma, você pode ter certeza de que ele decide algum idioma. Claramente, o idioma que ele decide é este: tente digitar . Veja se mais de 1/2 dos caminhos aceitam (ou mais de 1/2 seqüências aleatórias fazem com que ele aceite). Se assim for, . Se não, . Então, nós definimos uma linguagem usando esta TM.x L x LxxLxL

Por outro lado, se eu lhe der uma TM probabilística afirmando que é uma máquina de RP que decide algum idioma, você não pode nem ter certeza de que ele decide qualquer idioma. O problema é que, quando você observa apenas alguns caminhos aceitando, não sabe se está em ou não. Então, se eu lhe der uma máquina RP, você apenas terá que aceitar minha palavra. De fato, verificar se esta máquina define um idioma é incontestável.LxL

Quanto à sua segunda pergunta, para as classes sintáticas geralmente há um problema completo óbvio, como "Dada a máquina M, decida se ela aceita a tempo T na entrada x". Se você recebe uma máquina não determinística, esse problema é NP-completo, se é uma máquina PP, então é PP-completo, etc. O problema completo óbvio para as classes semânticas é indecidível, como mencionei. Portanto, não temos um problema completo gratuitamente para classes semânticas. Mas uma classe semântica pode ter um problema completo. Por exemplo, se P = BPP (como se acredita amplamente), o BPP tem uma caracterização sintática.

Edição : Como há alguma discussão sobre como definir classes semânticas e sintáticas, eu gostaria de ressaltar que Papadimitriou fornece uma definição em seu livro ao falar sobre linguagens folclóricas. (Veja minha pergunta sobre idiomas de folha para algumas referências.)

Ele diz que as classes sintáticas são aquelas para as quais existe alguma linguagem que define a classe usando a técnica da linguagem da folha. Classes semânticas são aquelas para as quais todas essas caracterizações exigem problemas promissores. Essa é uma definição rigorosa, mas funciona apenas para os idiomas que possuem caracterizações de idioma de folha.

Robin Kothari
fonte
3
Bem, eu não teria desperdiçado os últimos 20 minutos escrevendo minha resposta, se tivesse acabado de recarregar a página ... :) Vou deixar para o caso de também ser útil.
Ryan Williams
Sim, eu odeio quando isso acontece. Embora às vezes recebo a notificação "novas respostas foram postadas" no meio da composição de uma resposta.
Robin Kothari
6
@Robin: Você não teve que recorrer à afirmação "P = BPP" não comprovada, mas amplamente acreditada, como exemplo de uma classe semântica intensional que acaba sendo sintática: IP = PSPACE. (E agora qip também.)
Joshua Grochow
3
@ Josué: Você está certo, IP = PSPACE funciona.
Robin Kothari
11
@ Josué: Obrigado por mencionar o resultado IP = PSPACE. Eu nunca vi isso desse ponto de vista!
MS Dousti 22/09/10
28

PPRP PP>1/2x

PNPPPRPRP>1/2RPPromiseRP

P=BPPP=BPP

Se foi realmente o caso de simplesmente não existir uma lista facilmente computável de máquinas (de qualquer tipo razoável) que aceitem exatamente sua classe, então sim, não acho que sua classe possa ter uma linguagem completa. Mas isso parece muito difícil de formalizar adequadamente, e muito menos provar.

Ryan Williams
fonte
Oi Ryan. Você acha que é possível definir sintática-assumindo algo como a Tese de Church-Turing?
Kaveh
11
Eu editei minha resposta agora para abordar a questão de como definir sintaxe.
Robin Kothari