La prueba de Yao

Dejar${\displaystyle P}$sea ​​un polinomio, y${\displaystyle S=\{S_{k}\}_{k}}$ser una colección de conjuntos${\displaystyle S_{k}}$de${\displaystyle P(k)}$secuencias de -bits de longitud, y para cada${\displaystyle k}$, dejar${\displaystyle \mu _{k}}$sea ​​una distribución de probabilidad en${\displaystyle S_{k}}$, y${\displaystyle P_{C}}$ser un polinomio. Una colección predictiva${\displaystyle C=\{C_{k}\}}$es una colección de circuitos booleanos de tamaño menor que${\displaystyle P_{C}(k)}$. Dejar${\displaystyle p_{k,S}^{C}}$sea ​​la probabilidad de que en la entrada${\displaystyle s}$, una cadena seleccionada aleatoriamente en${\displaystyle S_{k}}$con probabilidad${\displaystyle \mu (s)}$,${\displaystyle C_{k}(s)=1}$, es decir

Además, dejemos${\displaystyle p_{k,U}^{C}}$sea ​​la probabilidad de que${\displaystyle C_{k}(s)=1}$en la entrada${\displaystyle s}$a${\displaystyle P(k)}$Secuencia de bits de longitud seleccionada uniformemente al azar en${\displaystyle \{0,1\}^{P(k)}}$Decimos que${\displaystyle S}$supera la prueba de Yao si para todas las predicciones de colección${\displaystyle C}$, para todos excepto para un número finito de personas${\displaystyle k}$, para todo polinomio${\displaystyle Q}$ :

Como en el caso de la prueba del siguiente bit , la colección predictiva utilizada en la definición anterior puede reemplazarse por una máquina de Turing probabilística que opera en tiempo polinomial. Esto también proporciona una definición estrictamente más fuerte de la prueba de Yao (véase el teorema de Adleman ). De hecho, se podrían determinar propiedades indecidibles de la secuencia pseudoaleatoria con los circuitos no uniformes descritos anteriormente, mientras que las máquinas BPP siempre pueden simularse mediante máquinas de Turing deterministas de tiempo exponencial .