Variantes de teoremas de producto directo

11

Un teorema directo del producto, informalmente, dice que calcular instancias de una función es más difícil que calcular una vez.kff

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 .fspkfs<spk

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 ?pkffspkfpO(ks)

(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)?fskf

Cualquier referencia sería apreciada.

usuario686
fuente

Respuestas:

10

(1): Ronen Shaltiel estudió esta pregunta en el artículo "Hacia la demostración de fuertes teoremas de productos directos", y resulta que tal conjetura es falsa: por ejemplo, podría ser que se pueda calcular con probabilidad con un tamaño mucho más pequeño que , y solo la masa de probabilidad adicional requiere el tamaño . En tal caso, al calcular en instancias, el circuito podría resolver en la mayoría de las instancias con un tamaño mucho menor que , y necesitará el tamaño solo en algunas de las instancias.0.99 p s 0.01 p s f k f s sf0.99ps0.01psfkfss

(2): Se conoce un teorema de producto directo para la complejidad del peor de los casos para las fórmulas y para los circuitos monótonos, pero en realidad se sabe que es falso para los circuitos generales. Para un ejemplo sencillo, considere una función que ve su entrada como un vector y la multiplica por una matriz booleana fija . Luego, calcular la función puede requerir un tamaño , pero calcularla en instancias se puede hacer mucho más rápido que utilizando un algoritmo de multiplicación de matrices. Puede encontrar una discusión exhaustiva sobre este tema en el libro "La complejidad de las funciones booleanas" de Ingo Wegener. Consulte el Capítulo 10.2 aquí: n × n f n 2 n n 3f:{0,1}n{0,1}nn×nfn2nn3http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ .

O meir
fuente
Eché un vistazo al Capítulo 10.2 del libro de Wegener (¡gracias por la referencia!) Que muestra que un resultado de suma directa no puede mantenerse en general. Pero, ¿se sabe algo para específica (tal vez aquellos que tienen una complejidad de circuito menor que )? (Todavía estoy interesado en la complejidad del peor de los casos y en los circuitos arbitrarios.)2 nf2n
usuario686
También me interesaría si se conocen resultados más débiles, por ejemplo, que calcular copias de requiere un tamaño ...f s + O ( k )kfs+O(k)
user686
Para funciones que tienen una complejidad de circuito menor que , consulte el ejemplo anterior con la multiplicación de matrices. En cuanto al resultado más débil que menciona, dicho resultado es trivial, ya que para calcular copias de , debe agregar al menos cables de salida al circuito que computa en una instancia. k f k f2nkfkf
O Meir el
7

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.

Dana Moshkovitz
fuente