Classes de complexité sémantique et syntaxique

Papadimitriou écrit dans son livre "Computational Complexity":

RP est en quelque sorte un nouveau type de classe de complexité inhabituel. Nulle machine de Turing non déterministe à bornes polynomiales ne peut être à la base de la définition d’un langage dans RP. Pour qu'une machine N définisse une langue dans RP , elle doit avoir la propriété remarquable de rejeter à toutes les entrées soit à l’ unanimité , soit à la majorité . La plupart des machines non déterministes se comportent autrement pour au moins quelques entrées ... Il n'y a pas de moyen facile de savoir si une machine s'arrête toujours avec une sortie certifiée. Nous appelons de manière informelle de telles classes sémantiques , par opposition aux classes syntaxiques telles que P et NP, où nous pouvons immédiatement dire par un contrôle superficiel si une machine correctement normalisée définit effectivement un langage de la classe.

Plusieurs pages plus tard, il souligne que:

le langage L est dans la classe PP s'il existe une machine de Turing N à borne polynomiale non déterministe telle que, pour toutes les entrées x, ssi plus de la moitié des calculs de N sur l'entrée x finissent par être acceptés. Nous disons que N décide L à la majorité .$x \in L$

Question 1: Pourquoi Papadimitriou conclut-il que PP est une classe syntaxique alors que sa définition n’est que légèrement différente de celle de RP ?

Question 2: Est-ce que le fait d'être "sémantique" pour une classe de complexité équivaut à ne pas avoir de problèmes complets ou si l'absence de problèmes complets est considérée comme une propriété que nous supposons que les classes sémantiques possèdent?

Modifier: voir la rubrique associée Toutes les classes de complexité ont-elles une caractérisation du langage feuille?

$x \in L$$x \notin L$$\geq 1/2$$< 1/2$

$x$$x \in L$$x \notin L$

$x$$L$

En ce qui concerne votre deuxième question, pour les classes syntaxiques, il existe généralement un problème complet évident, qui est le suivant: "Étant donné la machine M, décidez si elle accepte dans le temps T sur l’entrée x." Si on vous donne une machine non déterministe, ce problème est NP-complet, si c'est une machine PP, alors c'est PP-complet, etc. Le problème évident pour les classes sémantiques est indécidable, comme je l'ai mentionné. Donc, nous n'obtenons pas un problème complet gratuitement pour les cours sémantiques. Mais une classe sémantique peut avoir un problème complet. Par exemple, si P = BPP (comme on le croit généralement), alors BPP a une caractérisation syntaxique.

EDIT : Puisqu'il est question de définir des classes sémantiques et syntaxiques, j'aimerais préciser que Papadimitriou donne une définition dans son livre lorsqu'il parle des langages de feuilles. (Voir ma question sur les langages de feuille pour quelques références.)

Il dit que les classes syntaxiques sont celles pour lesquelles il existe un langage qui définit la classe en utilisant la technique du langage feuille. Les classes sémantiques sont celles pour lesquelles toutes ces caractérisations nécessitent des problèmes de promesse. Cette définition est rigoureuse, mais ne fonctionne que pour les langues ayant des caractérisations de langage feuille.

$PP$$RP$ $PP$$> 1/2$$x$

$P$$NP$$PP$$RP$$RP$$> 1/2$$RP$$Promise-RP$

$P=BPP$$P=BPP$

S'il était vraiment vrai qu'il n'y a tout simplement pas de liste facilement calculable de machines (de quelque sorte que ce soit) acceptant exactement votre classe, alors oui, je ne pense pas que votre classe puisse éventuellement avoir un langage complet. Mais cela semble très difficile à formaliser correctement, et encore moins à prouver.