O que há de errado com esse argumento

Não se acredita que seja o seguinte:

$\mathsf{L} \subseteq \mathsf{L}-\mbox{uniform } \mathsf{NC}^1$

Você pode me ajudar a ver onde o argumento termina?

O problema de acessibilidade direcionada está completo para . Argumento que está em -uniforme . $\mathsf{L}$ $\mathsf{L}$ $\mathsf{NC^1}$

O problema de alcançabilidade direcionada sobre os gráficos de configuração da máquina de Turing determinística no espaço de log está completo para . $\mathsf{L}$

O problema de acessibilidade direcionada está em $\mathsf{MSO}_2$ :

dados $s$ e $t$ , deixe $P$ representar a variável $\mathsf{MSO}$ para as arestas no caminho. Temos de verificar que $P$ contém um caminho dirigido de $s$ a $t$ o que pode ser feito através da verificação de que o em graus e para fora graus (em $P$ ) de cada incidente vértice sobre um bordo em $P$ é $1$ , excepto para $s$ e $t$ que ter em grau, grau = $0,1$ e $1,0$ respectivamente.

Toda floresta é um gráfico da largura da árvore $1$ . Em particular, o gráfico de configuração de uma Máquina de Turing determinística no espaço de log é uma estrutura delimitada na largura da árvore.

Nas versões de Elberfeld, Jakoby e Tantau do Logspace dos teoremas de Bodlaender e Courcelle :

$\mathsf{MSO}$ fórmula sobre estruturas limitadas da largura da árvore pode ser avaliada no espaço de log.

A prova é mais ou menos assim: para um determinado tamanho de estrutura , um limite na largura da árvore das estruturas e uma fórmula com vocabulário , construa (em ) construir um circuito . $n$ $w$ $\mathsf{MSO}$ $\varphi$ $\tau$ $\mathsf{L}$ $\#\mathsf{NC}^1$ $C$

O circuito dada uma estrutura de tamanho e árvore de largura, no máximo, , conta o número de "satisfazem" atribuições de em . $C$ $M$ $n$ $w$ $\varphi$ $M$

(O histograma que tabula o número de atribuições para as variáveis livres de segunda ordem em parametrizou nos tamanhos dos conjuntos de valores obtidos pelas variáveis). $\varphi$

Eu acho que o circuito depende apenas do vocabulário , do limite da largura da árvore de e do tamanho da estrutura . $C$ $\tau$ $d$ $n$

A prova prossegue avaliando o circuito em mas não precisamos dessa parte. $\#\mathsf{NC}^1 \subseteq \mathsf{L}$

Para nós, basta observar que, em Computação não determinística $\mathsf{NC^1}$ de Caussinus-Mackenzie-Therien-Vollmer:

todo circuito pode ser interpretado como contando o número de árvores de prova de um . $\#\mathsf{NC}^1$ $\mathsf{NC}^1$

Portanto, o circuito correspondente gera se a estrutura de entrada fórmula . $1$ $\mathsf{MSO}$

Pelo exposto acima, parece que o espaço de log é pelo menos em espaço de log uniforme $\mathsf{NC}^1$

cc.complexity-theory graph-algorithms complexity-classes descriptive-complexity finite-model-theory SamiD
fonte

Seu argumento de acessibilidade do MSO não está certo: ele funcionará apenas se o subgráfico induzido pelos vértices

for um caminho direcionado, o que não é o caso em geral (um contra-exemplo trivial é um par simétrico de arestas direcionadas). A maneira correta de alcançar a acessibilidade no MSO é afirmar que todo conjunto de vértices que contém

e é fechado na relação de aresta também inclui

P

$P$

s

$s$

t

$t$

David Richerby

@SamiD Dei o menor contra-exemplo, que passa a ser um gráfico simétrico. Mas o gráfico de 3 vértices com arestas direcionadas

funciona da mesma maneira: o caminho direcionado exclusivo de

mas o conjunto

não satisfaz sua fórmula porque, no subgráfico induzido por

(que é o gráfico inteiro),

a \to b

$a\to b$

b \to c

$b\to c$

c \to a

$c\to a$

a

$a$

c

$c$

a b c

$abc$

{a, b, c}

$\{a,b,c\}$

{a, b, c}

$\{a,b,c\}$

a

$a$ não possui zero grau e

não possui zero grau.

c

$c$

David Richerby

@ David Point bem-feito - minha formulação original era de buggy - espero que esteja tudo bem: considero um conjunto de arestas em vez de vértices e observo o grau de vértices em relação a essas arestas - elas devem ser as mesmas de antes. Obrigado pelo exemplo.

SamiD 28/10

@ Kaveh Obrigado pelas alterações - elas tornam a pergunta mais legível. Esclarei a questão que você levantou - no meu entender, a EJT cria um circuito aritmético com profundidade de log em L e, em seguida, o problema cai em L por causa da contenção CMTV # NC1 \ subseteq L. Mas paramos no momento em que o circuito é criado e sintaticamente converta-o em um circuito NC ^ 1. A conversão etc pode ser feita facilmente. Eu converti NC ^ 1 / poly em L-uniforme NC ^ 1 também porque é mais preciso.

samid

@Kaveh: 1. Alterar todos os

-circuito

para

criará um circuito

tal que

conte o número de árvores de prova de

+

$+$

# N C^{1}

$\#NC^1$

C

$C$

\lor

$\vee$

*

$*$

\land

$\wedge$

N C^{1}

$NC^1$

C^{'}

$C'$

C

$C$

C^{'}

$C'$

SamiD 29/10

O que há de errado com esse argumento

Respostas: