Preguntas etiquetadas con uniformity

31
¿Está

Pensé en compartir esta pregunta, ya que podría ser interesante para otros usuarios aquí. Suponga que una función que está en una clase uniforme (como ) también está en una pequeña clase no uniforme (como A C 0 / p o l y , es decir, no uniforme A C 0 ), ¿esto implica que la función está contenida...

27
¿Hay un candidato para un problema natural en

Quiero saber si la falta de uniformidad ayuda a las funciones informáticas en la práctica. Es fácil mostrar que hay funciones en , tome cualquier función no calificable y considere el lenguaje { }, que claramente tiene -circuitos uniformes, pero no es computable de manera uniforme en absoluto, pero...

12
¿P / poly

N P ⊆ P / p o l yP/poly=NP/polyP/poly=NP/polyP/poly = NP/poly implica , que a su vez tiene consecuencias interesantes como el colapso de la jerarquía polinómica.NP⊆P/polyNP⊆P/polyNP \subseteq P/poly ¿Hay implicaciones interesantes para ?P/poly≠NP/polyP/poly≠NP/polyP/poly \neq...