Determinantes e multiplicação de matrizes - Semelhança e diferenças na complexidade algorítmica e no tamanho do circuito aritmético

11

Estou tentando entender a relação entre a complexidade algorítmica e a complexidade do circuito de Determinantes e Multiplicação de Matrizes.

Sabe-se que o determinante de um matriz pode ser calculado em ~ O ( H ( n ) ) de tempo, em que M ( N ) é o tempo mínimo necessário para multiplicar quaisquer dois n × n matrizes. Sabe-se também que a melhor complexidade de circuito dos determinantes é polinomial na profundidade O ( log 2 ( n ) ) e exponencialn×nO~(M(n))M(n)n×nO(log2(n)) na profundidade 3. Mas a complexidade do circuito de multiplicação de matrizes, para qualquer profundidade constante, é apenas polinomial.

Por que existe uma diferença na complexidade do circuito para determinantes e multiplicação de matrizes, enquanto se sabe que, de uma perspectiva de algoritmo, o cálculo determinante é semelhante à multiplicação de matrizes? Especificamente, por que as complexidades do circuito possuem um intervalo exponencial na profundidade ?3

Provavelmente, a explicação é simples, mas não a vejo. Existe uma explicação com 'rigor'?

Veja também: Menor fórmula conhecida para o determinante

T ....
fonte

Respostas:

3

Considere o problema do valor do circuito e a avaliação da fórmula booleana para várias classes de complexidade pequena. A complexidade de tempo sequencial determinística deles é a mesma que sabemos, mas eles são muito diferentes da perspectiva da complexidade do circuito. A semelhança em um tipo específico de recurso em um modelo não implica similaridade para outros recursos em outros modelos. Um problema pode ser tal que possamos explorar a computação paralela para um, enquanto não podemos fazer isso para outro, mas a complexidade sequencial do tempo pode ser a mesma.

Quando podemos esperar uma relação mais robusta entre a complexidade de dois problemas entre modelos e recursos diferentes? Quando há uma redução robusta entre eles nas duas direções, que respeita os recursos nesses modelos.

NLNC2

Kaveh
fonte
O(n3)n2
1
TC0AC0
Eu estou olhando apenas a complexidade seqüencial por enquanto.
T ....
Não tenho certeza se sigo seu comentário. Acho que meu post responde à pergunta no cenário booleano (a pergunta não mencionou circuitos aritméticos originalmente IIRC). Para a configuração do circuito aritmético, não sei muito, espero que outros respondam à pergunta.
Kaveh 18/05
2

Eu diria que a lacuna nas configurações aritméticas nos diz que a multiplicação da matriz é inerentemente uma tarefa muito mais paralela que o determinante. Em outras palavras, enquanto as complexidades sequenciais de ambos os problemas estão intimamente relacionadas, suas complexidades paralelas não são tão próximas umas das outras.

D(n)n×n

O(logn)D(n)O(log2n).
3(AB)ij=kAikBkj
Bruno
fonte
Não sei se isso é uma resposta a "por que as complexidades do circuito têm um intervalo exponencial na profundidade 3?", Mas pelo menos você tem uma prova desse fato é o artigo de Csanky.
1955 Bruno
Se bem entendi, você está sugerindo: para ter um número polinomial de processadores, é preciso profundidade logarítmica?
T ....
1
Não me lembrava do modelo exato que Csanky usava. Na verdade, ele está considerando o que hoje chamamos de circuitos aritméticos com fan-in limitado . Assim, o limite inferior é bastante trivial e minha comparação com a multiplicação de matrizes não é relevante.
Bruno