É

Eu pensei em compartilhar esta pergunta, pois pode ser interessante para outros usuários aqui.

Assume-se que uma função que é de uma classe uniforme (como ) também está em uma pequena classe não uniforme (como , isto é, não uniforme ), isso implica que a função está contido numa classe uniforme menor (como )? Se a resposta a esta pergunta for positiva, qual é a menor classe de complexidade uniforme que contém ? Se negativo, podemos encontrar um contra-exemplo natural interessante? $NP$ $AC^0/poly$ $AC^0$ $P$ $NP \cap AC^0/poly$

É contida em ? $AC^0/poly \cap NP$ $P$

Nota: um amigo já respondeu parcialmente à minha pergunta offline, adicionarei a resposta se ele não a adicionar.

A questão é minha segunda tentativa de formalizar a seguinte pergunta informal:

A não uniformidade pode nos ajudar a computar problemas uniformes naturais?

Relacionado:

Existe um candidato para um problema natural em ? $P/poly−P$

cc.complexity-theory circuit-complexity uniformity Kaveh
fonte

@Kaveh: Talvez uma pergunta interessante seria a de pedir um problema natural em P / poli e NP, mas não em P. (Ou talvez isso é muito fácil?)

Robin Kothari

@Robin: que parece interessante, mas não estou certo de que seria mais fácil encontrar um problema natural em

N P \cap P / p o l y - P

$NP \cap P/poly - P$

Kaveh

N E X P \neq E X P

$NEXP \neq EXP$

N T i m e (f) \neq D T i m e (f)

$NTime(f) \neq DTime(f)$

f

$f$

A C^{0} / p o l y

$AC^0/poly$

n

$n$

n

$n$

@ Kaveh: Talvez você queira dar uma olhada na classe YP, definida por Scott Aaronson. É como P / poli, mas o "conselho" não é confiável. Em outras palavras, é como NP cruzar o coNP, mas a testemunha pode depender apenas do comprimento da entrada. YP está em P / poli e é uma classe uniforme. Talvez um problema no YP, mas não no P, seja um exemplo do problema que você está procurando. Seria natural, uniforme, não em P, em P / poli, e possivelmente não trivial, pois o conselho deve ser verificado pelo circuito.

Robin Kothari

@Kaveh: A classe YP ("Yoda Polynomial-Time") é definida formalmente no artigo de Scott "A Aprendizagem dos Estados Quânticos" [quant-ph / 0608142]

Alessandro Cosentino

Respostas:

$\Lambda \in NE \setminus E$ $L = \{x : |x| \in \Lambda\}$ $\Lambda \in NE \setminus E$ $L \in NP \setminus P$ $L \in AC^0/poly$

Yuval Filmus
fonte

Boa resposta Yuval!

Dai Le

Essencialmente, a mesma transformação é usada no Livro 1974 para mostrar que E ≠ NE se e somente se NP ∖ P contém uma linguagem de registro.

Tsuyoshi Ito 30/01

| x |

$|x|$

x

$x$

x

$x$

| x |

$|x|$

| x |

$|x|$

| x |

$|x|$

Λ

$\Lambda$

Responda à sua primeira pergunta: parece improvável.

$NP \cap AC^0/poly \subseteq P$ $NEXP = EXP$

$C$ $C$ $C(0^n) C(0^{n-1}1) C(0^{n-2}10) \cdots C(1^n)$

$C$ $n$ $NEXP$

Agora considere o idioma

$L =$ $1^n |$ $n$

$L$ $AC^0/poly$ $1^n$ $L$ $n$

$L$ $NP$ $n$ $\log n$ $O(n)$ $O(n)$

$L \in P$ $NEXP=EXP$ $O(n^c)$ $\log n$

Sua segunda pergunta está aberta (e aberta).

Ryan Williams
fonte

Por que você precisa resolver algum problema completo?

Yuval Filmus

Pensei que isso tornasse o argumento mais fácil de seguir.

Ryan Williams

Obrigado, Ryan, pela sua boa resposta e pela explicação. Acho que você não se importaria se eu aceitasse a resposta de Yuval, embora você tenha sido a primeira pessoa a postar.

Kaveh

Para a pergunta de Kaveh "A não uniformidade pode nos ajudar a calcular problemas uniformes naturais?"

$n$ $1$ $n$ $n^5$ $n$

Referências:

Friedhelm Meyer auf der Heide, " Um algoritmo de pesquisa linear polinomial para o problema da mochila n-Dimensional ", 1984

Stasys
fonte

n

$n$

2

$2$

2^{n}

$2^n$

1

$1$

N P \subseteq P / p o l y

$NP\subseteq P/poly$

@ Kaveh: Mas o NP em si é um grande OR de P. A "versão temporal" de P vs. NP é: podemos substituir esse OR grande por uma árvore de decisão algébrica determinística de profundidade polinomial (com P nas folhas)? Lembre-se de que a profundidade trivial para Subset-Sum é 2 ^ n (não n). Dopkin e Lipton (1978) mostraram que a profundidade n ^ 2/2 é necessária, e acreditava-se amplamente que isso pode ser melhorado para n ^ k para qualquer k. Mayer auf der Heide refutou essa crença: k = 5 é suficiente. Assim, a não uniformidade PODE ajudar, se estivermos interessados em profundidade (tempo).

Stasys