Preguntas etiquetadas con complexity

8
Circuito complejo y pruebas estadísticas

Hace unos años, tomé una clase sobre teoría de la complejidad de Steven Rudich, y recuerdo que él dio una conferencia interesante que conecta las pruebas estadísticas (¡como se encuentra en los departamentos de estadística!) Con la complejidad del circuito. Lo recuerdo afirmando algo vagamente...

8
Resultados condicionales que implican dificultades para mejorar los límites superior / inferior para permanente

Deje ser una matriz cuadrada dada. ¿Hay alguna evidencia de que superar los límites inferiores cuadráticos para B de modo que det ( B ) = per ( A ) pueda ser difícil?AAABBBdet(B)=per(A)det(B)=per(A)\text{det}(B) = \text{per}(A) ¿Hay alguna conjetura plausible que implique que probar límites más...

8
¿El rango de tensor está en VNP?

¿Se sabe si el rango de tensor de los tensores tridimensionales se encuentra en VNP (clase valiente no determinista)? En caso afirmativo, ¿qué se sabe sobre el rango de tensor de alta dimensión? De hecho, estoy interesado en un problema mucho más simple. Me gustaría saber si se pueden construir...

8
Complejidad de clasificación

No es difícil mostrar que ordenar una matriz de números es difícil para . Si la entrada es una matriz de 1s y 0s, entonces es esencialmente la función C o u n t (dados n bits, genera el número de 1s en binario) ya que C o u n t está completo para T C 0 y es posible para convertir números unarios en...