¿Cuál es la clase de complejidad "más pequeña" para la cual un

Creo que las respuestas a esta pregunta dan clases tales que para todos los polinomios , hay un problema en la clase que no tiene circuitos de tamaño . Sin embargo, estoy preguntando sobre el tamaño del circuito . $p$
$p(n)$
$\omega \hspace{.02 in}(n)$

$\big(\hspace{-0.07 in}\left\langle \hspace{-0.04 in}0^{\hspace{.02 in}0}\hspace{-0.03 in},\hspace{-0.04 in}1^{\hspace{-0.03 in}1}\hspace{-0.03 in},2^{\hspace{.02 in}2}\hspace{-0.04 in},\hspace{-0.03 in}3^1\hspace{-0.04 in},\hspace{-0.03 in}4^4\hspace{-0.03 in},\hspace{-0.03 in}5^1\hspace{-0.04 in},\hspace{-0.03 in}6^{\hspace{.03 in}6}\hspace{-0.03 in},\hspace{-0.03 in}7^1\hspace{-0.03 in},\hspace{-0.03 in}8^8\hspace{-0.03 in},\hspace{-0.03 in}9^1\hspace{-0.03 in},...\hspace{-0.05 in}\right\rangle \:$ es superlineal pero no . Aunque este comportamiento par-impar podría manejarse con relleno, uno podría tener rayas extremadamente largas de valores súper polinomiales entre valores bajos). $\omega \hspace{.02 in}(n)$

circuit-complexity lower-bounds Comunidad
fuente

Creo que los límites inferiores superlineales significan que hay un límite inferior en .

ω (n)

$\omega(n)$

Kaveh

No creo que llamemos a eso una función superlineal. Hasta donde sé, lo que la gente entiende por superlineal es la misma manera que sublinear es . ¿Tiene alguna referencia para el uso de superlineal en su sentido? Su secuencia es infinitamente a menudo superlineal pero no es superlineal.

ω (n)

$\omega(n)$

o (n)

$o(n)$

Kaveh

Creo que el uso estándar es que "tamaño de circuito superlineal" significa que no tiene circuitos de tamaño

, es decir, con una frecuencia infinita. Los límites inferiores "casi en todas partes" son mucho más raros y mucho más difíciles de lograr.

O (n)

$O(n)$

Joshua Grochow

Vea la publicación del blog de Fortnow sobre la cuestión de cuál es la definición correcta de la notación omega grande.

Robin Kothari

@Kaveh: Lo siento, debería haber sido más específico. Quise decir que "el problema X no tiene circuitos de tamaño lineal" es generalmente equivalente a decir que "el problema X tiene un límite inferior de tamaño de circuito superlineal ", y creo que ambos significan (y deberían significar) lo que dije en mis comentarios anteriores La frase "el problema X tiene circuitos de tamaño superlineal" me parece extraña, porque "tener tales y tales circuitos" es un límite superior, pero "

superlineal

Respuestas:

Se sabe que y no tienen circuitos para ningún k fijo y no existe una contención conocida entre ellos. Detalles en miblog. $S^p_2$ $PP$ $n^k$

Actualización: como señala Rickey Demer, estos resultados no necesariamente dan un lenguaje con un límite inferior para todos los en . Creo que el es probablemente el más conocido. Dado que tiene conjuntos completos, es posible que pueda obtener un límite de todo , pero no tengo una prueba completa. $n$ $S_2^p$ $\Delta^p_3$ $PP$ $n$

Lance Fortnow
fuente

¿Cómo se pasa de "no tiene n

circuitos -size" a un

tamaño del circuito límite inferior?

^{k}

$^k$

ω (n)

$\omega(n)$

$\hspace{.84 in}$ Ver la parte superior de esta página para una secuencia que no tiene límite superior polinomio pero no es

ω (n)

$\omega(n)$

$\hspace{.58 in}$

@ EmilJeřábek: ¿Cómo se consigue eso para todos los

suficientemente grandes en lugar de solo para infinitos

n

$n$

n

$n$

$\hspace{.08 in}$ (Eso sería necesario para obtener "el tamaño del circuito es

" en lugar de "el tamaño del circuito no es

ω (n)

$\omega(n)$

O (n)

$O(n)$

$\hspace{1.12 in}$

@ EmilJeřábek: Véase mi respuesta a meta.stackexchange.com/a/293100/232555 .

Tienes razón, me estaba concentrando en la primera parte de la prueba que falta en el blog, y no me di cuenta de que hay un gran problema con la distinción de casos. Entonces, de todos modos, hay un lenguaje en

que necesita circuitos de tamaño

para todos los

suficientemente grandes .

Δ_{3}^{P}

$\Delta^P_3$

\geq n^{k}

$\ge n^k$

n

$n$

Emil Jeřábek

Puede obtener un límite inferior casi en todas partes para

. Para cada

, sea

el conjunto de todos los circuitos de tamaño

. Para

, llame al oráculo una vez para determinar cuál es la respuesta de la mayoría de los circuitos en

en la entrada número

de longitud

, y elimine de

todos los circuitos que dan esta respuesta (esto puede codificarse como una restricción polytime en la próxima llamada del oráculo). Nuestra función dura generará el valor opuesto en el

P^{P P [n^{2}]}

$P^{PP[n^2]}$

n

$n$

S

$S$

n \log n

$n\log n$

i = 1, \dots, n^{2}

$i=1,\ldots,n^2$

S

$S$

i

$i$

n

$n$

S

$S$

th entrada de longitud

.. Fin para. Ahora, dado un ae-lb para

, ¿podemos elevarlo a

i

$i$

n

$n$

P^{P P [n^{2}]}

$P^{PP[n^2]}$

P P

$PP$

Ryan Williams

Deje que dMCSP sea la versión decisiva del Problema de tamaño mínimo de circuito
y deje que "[1]" indique " solo 1 consulta ".
La respuesta a mi pregunta parece ser , Que de hecho es tal que para cada entero positivo k, tiene una $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)}$
Límite inferior: $\omega \hspace{-0.02 in}\big(\hspace{-0.03 in}n^k\hspace{-0.03 in}\big)$

Sigue el párrafo final de la página 7 de este documento , la de que en el párrafo ser uno más de este argumento , y, además, "observar que se trata de una" "tarea de decidir si co_dMCSP una tabla de verdad dada de longitud es difícil" , en el mismo sentido que el usado en ese párrafo de la página 7. Los DNF circuitos de una manera arbitraria longitud- tabla de verdad tienen un tamaño como máximo $k$ $k$
$\ell$

$\ell$ , así dMCSP está en . Por lo tanto $\ell^{\hspace{.03 in}2} \cdot \operatorname{polylog}(\ell)$
$\mathbf{NP}$ . $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)} \subseteq \mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}}\hspace{-0.03 in}\right)} \subseteq \mathbf{P}^{\left(\mathbf{NP}^{\hspace{.03 in}\mathbf{NP}}\hspace{-0.03 in}\right)} = \Delta^p_3$

No estoy al tanto de cualquier prueba de que cualquiera de esas s son igualdades, y este trabajo da obstrucciones significativas a la posibilidad de ser dMCSP -difícil bajo reducciones de Turing aleatorios. Las igualdades se seguirían de dMCSP siendo -difícil bajo fuerte no determinista ( página 6 ) reducción de una sola consulta que tienen una cadena de asesoramiento de tamaño polinomio que es computable por $\subseteq$ $\mathbf{NP}$
$\mathbf{NP}$
, Pero en particular no conozco ninguna prueba de tal dureza. $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)}$

fuente