"Complexidade matricial"

Enquanto navegava em postagens antigas do CStheory.se , deparei-me com uma fascinante publicação no blog sobre o problema da mortalidade matricial . A menos que eu tenha interpretado mal o problema, ele afirma que, dada uma coleção finita de matrizes 3 x 3 com entradas inteiras para cada valor da matriz, é preciso decidir se existe um produto finito dessas matrizes que seja igual a uma matriz composta por todos os zeros.

Surpreendentemente, esse problema é indecidível, devido a uma redução do problema de correspondência Post. Minha pergunta é: Dada a indecidibilidade do problema e seu vínculo com um problema vinculado às máquinas de Turing, é possível mostrar que existe uma maneira de caracterizar (por exemplo) todas as linguagens re, a classe P e a classe NP usando matrizes?

Eu mesmo trabalhei um pouco nisso, mas falta o treinamento para ter certeza se minha crença está correta. Acho que esse problema exigiria um pouco de trabalho da parte do leitor para resolver.

Não sei como usar o LaTeX para escrever matrizes no SE, mas aqui está minha primeira tentativa de caracterizar o NP:

$S$ $k$ $M$ $|M|^k + k$ $S$

Essa tentativa não está completa e inclui qualquer prova, como você vê, mas eu queria dar meus primeiros pensamentos sobre o problema para ver se uma tentativa mais sofisticada poderia ser feita para formalizar uma noção de complexidade da matriz. Isso é interessante porque, como a caracterização de NP por Fagin usando complexidade descritiva, poderia ser usado para caracterizar NP de maneira independente da máquina.

cc.complexity-theory matrix-product Philip White
fonte

O uso da terminologia "complexidade descritiva matricial" aqui tem algo a ver com complexidade descritiva? Parece-me que você está tentando expressar classes de complexidade usando operações de matriz, em vez de aplicar a teoria de modelos finitos. Nesse caso, convém remover a marca de complexidade descritiva. Também pode ser útil para nós se você esclareceu a distinção ou conexão entre sua ideia e a Complexidade Descritiva.

Mdxn

Não sou especialista, mas acreditava que a complexidade "descritiva" é nomeada como é porque é independente das máquinas de Turing. "Descritivo" não significa "lógico" ou "usando a teoria dos modelos finitos" - eu não acho. Eu adicionei a tag de complexidade descritiva porque a geração de caracterizações alternativas e independentes de máquina de classes de complexidade é o objetivo da complexidade descritiva.

Philip White

Embora a palavra comum em inglês "descritivo" não signifique "usar a lógica / teoria dos modelos finitos", o termo técnico "complexidade descritiva" significa isso.

David Richerby

Está bem. Eu vou mudar de questão.

Philip White

M_{1}, . . ., M_{n}

$M_1,...,M_n$

i_{k}

$i_k$

M_{i_{1}} \cdot . . . \cdot M_{i_{m}} = 0

$M_{i_1} \cdot ... \cdot M_{i_m} = 0$

m

$m$

T

$T$

x

$x$

m = O (f (| x |)^{k})

$m = O(f(|x|)^k)$

k

$k$

f (| x |)

$f(|x|)$

T

$T$

x

$x$

"Complexidade matricial" - é possível?

Respostas: