Problemas Sucintos em

O estudo da representação sucinta de gráficos foi iniciado por Galperin e Wigderson em um artigo de 1983, onde eles provam que, para muitos problemas simples como encontrar um triângulo em um gráfico, a versão sucinta correspondente no concluída. Papadimitriou e Yanakkakis aprofundam essa linha de pesquisa e provam que, para um problema que é -complete / -complete, a versão Succinct correspondente, ou seja, Succinct , respectivamente, -complete e -complete. (Eles também mostram que se é Π N P P Π N E X P E X P Π N L Π P S P A C $\mathsf{NP}$$\Pi$$\mathsf{NP}$$\mathsf{P}$$\Pi$$\mathsf{NEXP}$$\mathsf{EXP}$$\Pi$$\mathsf{NL}$-complete, então Succinct é -complete.$\Pi$$\mathsf{PSPACE}$

Agora, minha pergunta é: existem problemas conhecidos pelos quais, a versão Succinct correspondente está em ? Eu estaria interessado em saber sobre outros resultados relacionados (positivos e impossíveis, se houver) que eu poderia ter perdido acima. (Eu não consegui localizar nada de interesse em uma pesquisa no Google, pois palavras de pesquisa como sucinta, representação, problemas, gráficos levam a praticamente qualquer resultado de complexidade! :))$\Pi$$\mathsf{P}$

Aqui está um problema interessante cuja versão sucinta tem propriedades interessantes. Defina o tamanho do circuito como o problema: dada uma função booleana como uma sequência de 2 n bits, essa função possui um circuito de tamanho no máximo 2 n / 2 ? Note que este problema é em N P .$2^{n/2}$$2^n$$2^{n/2}$$NP$

Uma maneira de definir Succinct-Circuit-Size- seria: para uma constante k , dado um n -input, n k circuito -size C , queremos saber se sua tabela de verdade é uma instância de Circuit-Size - 2 n / 2 . Mas este é um problema trivial: todas as entradas que são circuitos reais são instâncias sim. Portanto, este problema está em P .$2^{n/2}$$k$$n$$n^k$$C$$2^{n/2}$$P$

Uma maneira mais geral de definir Succinct-Circuit-Size- seria: recebemos um circuito arbitrário C e queremos saber se sua tabela verdade codifica uma instância de Circuit-Size- 2 n / 2 . Mas se n é o número de entradas para C , m é o tamanho de C e m ≤ 2 n / 2 , podemos aceitar automaticamente: a entrada em si é uma testemunha do idioma. Caso contrário, temos m ≥ 2 n / 2 . Nesse caso, o comprimento de entrada $2^{n/2}$$C$$2^{n/2}$$n$$C$$m$$C$$m \leq 2^{n/2}$$m \geq 2^{n/2}$$m$é já grande, de modo que podemos tentar todos os possíveis atribuições em m O ( 1 ) o tempo, obter a tabela de verdade da função, e agora voltar ao original N P problema novamente. Portanto, este é um problema no N P cuja versão sucinta também está em N P .$2^n$$m^{O(1)}$$NP$$NP$$NP$

Este problema é acreditado ser não -Hard; veja o artigo de Kabanets e Cai (http://www.cs.sfu.ca/~kabanets/Research/circuit.html)$NP$

Dado que mesmo decidir se o gráfico representado por uma determinada representação sucinta contém pelo menos uma aresta é equivalente ao circuito SAT e, portanto, NP-completo, é tentador afirmar que qualquer propriedade interessante de uma representação sucinta deve ser NP-hard sob uma definição adequada de "interessante". Essa afirmação seria um análogo teórico da complexidade para o teorema de Rice . Infelizmente, encontrar o análogo teórico da complexidade mais geral do teorema de Rice é um problema em aberto , embora existam resultados que dão algumas formas de tais análogos teóricos da complexidade.

Não queria que isso fosse uma resposta, mas exigiria muitos comentários. Espero que seja útil.

Como Tsuyoshi aponta, é tentador conjeturar que todas as propriedades "não triviais" são difíceis (NP-difíceis, por exemplo). No entanto, para mostrar isso, você precisa definir não trivial. No teorema de Rice, as propriedades não triviais são todas as propriedades, exceto a propriedade que inclui todas as linguagens computáveis ​​enumeráveis ​​e a propriedade que não inclui nenhuma linguagem computável enumerável. É menos claro qual é a definição correta de não trivial para problemas sucintos. Definitivamente, as propriedades que contêm todas as seqüências ou não estão em P. Mas também existem outras em P. Por exemplo, a propriedade que corresponde a cadeias cujo bit do meio é 0. Ou Π contém todas as cadeias de 2 n bits, de modo que a cada 2 n /$\Pi$$\Pi$$2^n$$2^n/x$-th bit é 1, onde . Então, como definimos "trivial" para abranger esse tipo de propriedades?$x = n^{O(1)}$

Uma idéia é examinar aqueles que são "simétricos": se uma string s está em Π , qualquer permutação dos bits de s também está em Π . Tais propriedades dependem apenas do número de 1 bits em uma sequência. Em resposta à pergunta que Tsuyoshi fez, Ryan Williams fornece um link para este artigo, que mostra que todos esses problemas são difíceis.$\Pi$$s$$\Pi$$s$$\Pi$

Outras idéias como definir "propriedade não trivial"? Podemos considerar como uma família de funções booleanas (as funções indicadoras da propriedade para cada comprimento de string). Parece-me que as propriedades não triviais são aquelas para as quais a família correspondente de funções booleanas possui complexidade não trivial. Por exemplo, podemos mostrar que as propriedades cuja família de funções booleanas associada tem complexidade linear de árvore de decisão são difíceis?$\Pi$