Fondo
Las clases de complejidad BPP , BQP y QMA se definen semánticamente. Intentaré explicar un poco cuál es la diferencia entre una definición semántica y una sintáctica. La clase de complejidad P suele definirse como la clase de lenguajes aceptados en tiempo polinómico por una máquina de Turing determinista. Aunque en principio parece una definición semántica, $P$ tiene una caracterización sintáctica fácil, es decir, máquinas de Turing deterministas con un reloj que cuenta los pasos hasta un polinomio fijo (tome una máquina de Turing determinista, añádale un reloj polinómico tal que la nueva máquina calcule la longitud de la entrada $n$ entonces el valor del polinomio $p(n)$ y simular la máquina original para $p(n)$ pasos. Las lenguas aceptadas por estas máquinas estarán en $P$ y existe al menos una máquina de este tipo para cada conjunto en $P$ ). También existen otras caracterizaciones sintácticas para $P$ en complejidad descriptiva como $FO(LFP)$ lógica de primer orden con la mínimo punto fijo operador. La situación es similar para PP . Tener una caracterización sintáctica es útil, por ejemplo una caracterización sintáctica nos permitiría enumerar los conjuntos de la clase de manera efectiva, y si la enumeración es lo suficientemente eficiente, podemos diagonalizar contra la clase para obtener un resultado de separación como tiempo y espacio teoremas de jerarquía.
Mi pregunta principal es:
¿Existe una caracterización sintáctica para BPP, BQP o QMA?
También me gustaría conocer algún teorema de jerarquía temporal o espacial para las clases semánticas antes mencionadas.
La motivación de esta pregunta surgió de aquí . Utilicé Google Scholar, el único resultado que parecía relevante era una cita a una tesis de maestría titulada "Una caracterización lógica de la clase de complejidad computacional BPP y un algoritmo cuántico para concentrar el entrelazamiento", pero no pude encontrar una versión en línea de la misma.
