Un teorema directo del producto, informalmente, dice que calcular instancias de una función es más difícil que calcular una vez.
Los teoremas típicos de productos directos (p. Ej., El Lema XOR de Yao) analizan la complejidad de los casos promedio y argumentan (muy a grandes rasgos) que no puede calcularse mediante circuitos de tamaño con una probabilidad mejor que , entonces copias de no pueden calcularse mediante circuitos de tamaño con probabilidad mejor que .
Estoy buscando diferentes tipos de teoremas de productos directos (si se conocen). Específicamente:
(1) Digamos que arreglamos la probabilidad de error y en cambio estamos interesados en el tamaño del circuito necesario para calcular copias de ? ¿Hay un resultado que diga que si no puede ser calculado por circuitos de tamaño con probabilidad mejor que , entonces copias de no pueden ser calculadas con probabilidad mejor que usando un circuito de tamaño menor que ?
(2) ¿Qué se sabe con respecto a la complejidad del peor de los casos ? Por ejemplo, si no se puede calcular (con 0 error) por circuitos de tamaño , ¿qué podemos decir acerca de la complejidad de calcular copias de (con 0 error)?
Cualquier referencia sería apreciada.
Solo para complementar la respuesta de Or, se estudiaron preguntas sobre el sabor de (1) [cuánto de un recurso se necesita para obtener buenos resultados en k copias], y los teoremas correspondientes se denominan "teoremas de suma directa". Al igual que con los teoremas de producto directo, los teoremas de suma directa pueden o no ser válidos, dependiendo de la configuración.
fuente