Quais são as razões convincentes para acreditar em ?

23

Quais são as razões convincentes para acreditar em ? L é a classe de algoritmos de espaço de log com ponteiros para a entrada. $L\neq P$

Suponha L = P no momento. Como seria um algoritmo de espaço de log para um problema de P-complete em seus contornos gerais?

cc.complexity-theory complexity-classes Jumer
fonte

2

em certo sentido, seria um algoritmo de compactação de espaço para um cálculo de máquina de Turing em tempo P que usualmente ocupa espaço P. portanto, se L ≠ P, existe algum "(in) limite de compressibilidade" de P. uma possível direção de construção / pergunta / pesquisa com base nesse ângulo, compressão da sequência de execução da TM

vzn

1

ver também que separam L / P & kintalis post citada

vzn

28

O resultado de Mulmuley (da página de Mulmuley sem paywall) que, no modelo PRAM sem operações de bit, " ". (No modelo booleano comum em que vive, .) Esse modelo é forte o suficiente para que o resultado implique qualquer algoritmo para a problema completo deve ter uma aparência bem diferente dos algoritmos mais conhecidos para os problemas . $\mathsf{P} \neq \mathsf{NC}$ $\mathsf{L}$ $\mathsf{L} \subseteq \mathsf{NC}$ $\mathsf{L}$ $\mathsf{P}$ $\mathsf{P}$

O modelo PRAM sem operações de bit é um modelo algébrico não uniforme sobre (semelhante às árvores de computação algébrica ou ao modelo de RAM algébrica Blum - Shub - Smale) no qual o programa não uniforme pode depender não apenas do número de entradas inteiras, mas também em seu comprimento total de bits. Dessa forma, não é um modelo algébrico "puramente", mas vive em algum lugar entre algébrico e booleano. Este modelo inclui algoritmos de politempo para programação linear, maxflow, mincut, árvore de abrangência ponderada, caminhos mais curtos e outros problemas de otimização combinatória, o algoritmo de espaço de log para isomorfismo de árvore (ver comentários abaixo) e algoritmos para aproximar as raízes complexas de polinômios, é por isso que digo qualquer algoritmo para um $\mathbb{Z}$ $\mathsf{L}$ $\mathsf{P}$ Um problema completo (que, como sua pergunta indica, você sabe que a maioria das pessoas pensa que não existe) teria que parecer bem diferente de qualquer um deles.

Joshua Grochow
fonte

Em sua conjectura na página 62, como relaciona com o fluxo de custo mínimo? Por que tem que ser linear e uma bijeção? A conjectura parece não implicar nenhum mapa linear de classificação (já que o mapa inverso de um mapa linear de 1 a 1 é linear) avaliado no conjunto zero de pode cobrir . Minha interpretação está correta?

S L_{m} (C)

$SL_m(C)$

L

$L$

F

$F$

k

$k$

S L_{m} (C)

$SL_m(C)$

L (n)

$L(n)$

T ....

(Boa pergunta, mas parece um pouco ortogonal à pergunta que está sendo feita aqui ...) Sim. Qualquer coisa computável de forma eficiente no modelo PRAM sem operações de bit possui uma fórmula pequena , portanto (por Valiant) é uma projeção de det: . Em particular, iff iff .

φ

$\varphi$

φ (x) = det (F (x))

$\varphi(x) = \det(F(x))$

x \in L (n)

$x \in L(n)$

det (F (x)) = 1

$\det(F(x)) = 1$

x \in F^{- 1} (S L_{m})

$x \in F^{-1}(SL_m)$

Joshua Grochow

a única suposição é que parece ser o caso. Bastante interessante! Como acontece com outras pressuposições e provas dessa complexidade - É o contrário: se , é ? Eu nunca vi essas conversas na teoria da complexidade ou essas conversas não são possíveis?

d e t \notin N C^{1}

$det\notin NC^{1}$

d e t \in N C^{1}

$det\in NC^1$

P = N C

$P=NC$

T ....

@JAS: Não vejo o que você quer dizer com "a única suposição é ...": não acho que se segue que , se é isso que você estava dizendo ...

det \notin N C^{1} \Rightarrow P \neq N C

$\det \notin NC^1 \Rightarrow P \neq NC$

Joshua Grochow

1

@JAS: A crença de que apóia a conjectura, mas não implica a conjectura. Ele menciona o inverso, que, se uma correspondência perfeita , em seguida, a conjectura é falso para pequenas . Equivalentemente, se a conjectura for verdadeira, então a correspondência perfeita . Observe que esta é a direção oposta ao que você estava dizendo.

d e t \notin N C^{1}

$det \notin NC^1$

\in N C^{1}

$\in NC^1$

a

$a$

\notin N C^{1}

$\notin NC^1$

Joshua Grochow

15

Há uma série de trabalhos de M. Hofmann e U. Schöpp que formalizam a noção intuitiva de "algoritmos logarítmicos típicos do espaço", usando apenas um número constante de ponteiros para a estrutura de dados de entrada, como uma linguagem de programação PURPLE (programas de ponteiros puros com iteração.)

Mesmo que os programas PURPLE não capturem todos os (eles foram incapazes de decidir a conexão não direcionada st), sua extensão com contagem é mostrada para capturar uma grande fração de , mas não o problema P-completo Horn-SAT. Isso é mostrado no artigo mais recente da série: M. Hofmann, R. Ramyaa e U. Schöpp: Pure Pointer Programs and Tree Isomorphism, FOSSACS 2013. $\mathsf{L}$ $\mathsf{L}$

A conclusão parece ser que algoritmos de espaço logarítmico para problemas devem ser muito atípicos e ir além do que pode ser implementado no PURPLE com a contagem. $\mathsf{P}$

Jan Johannsen
fonte

5

ROXO com a contagem é um modelo interessante e corresponde à minha intuição ingênua de algoritmos de espaço de log. Mas não sei se esse resultado é uma boa evidência para : eles até dizem "Então, a satisfação de Horn não pode ser decidida em PURPLE aumentada com não-determinismo e contando também, mas pela mesma razão que um problema específico do LOGSPACE, a saber o isomorfismo das árvores não pode ". Isto essencialmente diz que o resultado é realmente sobre a fraqueza da contagem ROXO + (que corresponde à intuição ingênua de algos LOGSPACE), em vez da fraqueza de L ...

L \neq P

$L \neq P$

Joshua Grochow

3

A complexidade descritiva tentou fornecer algumas respostas.

FO (lógica de primeira ordem), com ord (ordenação do domínio) e TC (fecho transitivo) . $= L$

FO + ord + LFP (ponto fixo menos) . $= P$

Então surge a pergunta - FO + ord + TC FO + ord + LFP? $\subset$

Por outro lado, FO + LFP (sem ord) nem pode contar! Por exemplo, é incapaz de expressar o fato de que a cardinalidade do domínio é uniforme. Essa lógica certamente não pode capturar - mas a questão é: ela pode capturar ou ? $P$ $L$ $NL$

Veja, por exemplo, http://www.cs.umass.edu/%7Eimmerman/pub/EATCScolumn.pdf

E então, a lógica de segunda ordem (SO) + Horn captura P, enquanto SO + Krom captura NL. Veja Erich Gradel, Capturando classes de complexidade por fragmentos da lógica de segunda ordem , Teoria da Computação, 1992.

Martin Seymour
fonte

3

FO + LFP sem pedindo certamente não pode capturar , pela mesma razão que você cita: não pode contar, nem mesmo modulo 2.

L

$\mathsf{L}$

Jan Johannsen

Aceita. Então a pergunta (ou melhor, uma das perguntas) é - FO + LFP (sem ord) é um subconjunto estrito de FO + LFP (com ord)?

Martin Seymour

0

Isso não é realmente uma resposta, mas, como descrito aqui , acredito que para o problema completo de deve ser possível definir alguma "medida de complexidade" nas instâncias, para resolver uma instância de complexidade exigiria espaço . Se verdadeiro, isso implicaria a separação desejada; se identificarmos essa medida, parece possível alcançar a complexidade do espaço monótono das instâncias, e isso daria uma evidência tangível de que estamos no caminho certo - embora mostrar um limite não monótono seja aparentemente muito mais difícil. $\sf{P}$ $\sf{GEN}$ $k$ $\Theta(k \log n)$

NisaiVloot
fonte

Quais são as razões convincentes para acreditar em ?

Respostas: