Preguntas etiquetadas con circuit-complexity

21
¿

¿Existe alguna hipótesis plausible de complejidad / criptografía que descarte la posibilidad de que los circuitos de tamaño polinomial tengan circuitos de tamaño subexponencial (es decir, con ϵ < 1 ) de profundidad limitada ( d = O ( 1 ) )?2O ( nϵ)2O(nϵ)2^{O(n^\epsilon)}ϵ <...

20
Relación entre y lenguajes regulares

Deje que sea ​​la clase de todos los idiomas regulares.R E GREG\mathsf{REG} Se conoce y \ mathsf {REG} \ not \ subset \ mathsf {AC} ^ 0 . Pero, ¿hay alguna caracterización de idiomas en \ mathsf {AC} ^ 0 \ cap \ mathsf {REG} ?A C0 0⊄ R E GAC0⊄REG\mathsf{AC}^0 \not\subset \mathsf{REG}A C 0 ∩ R E GR...

19
Paridad y

La paridad y son como gemelos inseparables. O eso parece durante los últimos 30 años. A la luz del resultado de Ryan, habrá un renovado interés en las clases pequeñas.A C0 0AC0AC^0 Furst Saxe Sipser a Yao a Hastad son todas paridades y restricciones aleatorias. Razborov / Smolensky es un polinomio...

18
¿Es posible probar si un número computable es racional o entero?

¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...