Diferencia entre revisiones de «PSPACE»

27 bytes añadidos ,  hace 2 años
m
Mantenimiento de Control de autoridades
m (Mantenimiento de Control de autoridades)
 
Un importante resultado de la teoría de la complejidad es que '''PSPACE''' puede ser caracterizada como todas las lenguas reconocidas por la presencia de un sistema interactivo de la prueba (interactive proof system), una definición de la clase [[IP (clase de complejidad)|IP]]. En este sistema, hay una demostración que intenta convencer aleatoriamente en tiempo polinómico para verificar que una cadena pertenece al lenguaje. Debe ser capaz de convencer al verificador con una elevada probabilidad, si la cadena está en el lenguaje, pero no debería ser capaz de convencer con una baja probabilidad, si la cadena no está en el lenguaje.
 
{{Control de autoridades}}
[[Categoría:Clases de complejidad]]
1 220 679

ediciones