Capacidade do quebra-cabeça exclusivamente solucionável (USP)

Em seu trabalho seminal, algoritmos teóricos de grupo para multiplicações de matrizes , Cohn, Kleinberg, Szegedy e Umans introduzem o conceito de quebra-cabeça exclusivamente solucionável (definido abaixo) e a capacidade da USP. Eles afirmam que Coppersmith e Winograd, em seu próprio papel inovador A multiplicação de matrizes através de progressões aritméticas , "implicitamente" provar que a capacidade USP é $3/2^{2/3}$ . Essa afirmação é reiterada em vários outros lugares (inclusive aqui na história), mas em nenhum lugar há uma explicação para ser encontrada. Abaixo está meu próprio entendimento sobre o que Coppersmith e Winograd provam, e por que não é suficiente.

É verdade que a capacidade USP é $3/2^{2/3}$ ? Em caso afirmativo, existe uma referência para a prova?

Quebra-cabeças exclusivamente solucionáveis

Um quebra-cabeça exclusivamente solucionável (USP) de comprimento $n$ e largura $k$ consiste em um subconjunto de $\{1,2,3\}^k$ de tamanho $n$ , que também consideramos como três coleções de $n$ "peças" (correspondentes aos locais onde vetores são $1$ , os locais onde são $2$ e os locais onde são $3$ ), satisfazendo a seguinte propriedade. Suponha que organizemos todas as peças $1$ em $n$ linhas. Então deve haver uma maneira única de colocar as outras peças, uma de cada tipo em cada linha, para que elas "se encaixem".

Seja $N(k)$ o comprimento máximo de um USP de largura $k$ . A capacidade da USP é

$$\kappa = \sup_k N(k)^{1/k}.$$ Em uma USP, cada uma das peças precisa ser única - isso significa que não há duas linhas que contêm o símbolo $c \in \{1,2,3\}$ exatamente nos mesmos lugares. Isto demonstra que (após um curto argumento) que e por issok≤3/22/3. $$N(k) \leq \sum_{a+b+c=k} \min \left\{ \binom{k}{a}, \binom{k}{b}, \binom{k}{c} \right\} \leq \binom{k+2}{2} \binom{k}{k/3},$$ $\kappa \leq 3/2^{2/3}$

Exemplo (um USP de comprimento e largura 4 ): 1111 2131 1213 2233 Não exemplo de comprimento 3 e largura 3 , em que as peças 2 e 3 podem ser dispostas de duas maneiras diferentes: $4$$4$

$$\begin{align*} 1111 \\ 2131 \\ 1213 \\ 2233 \end{align*}$$ $3$$3$$2$$3$ $$\begin{align*} 123 && 132 \\ 231 && 321 \\ 312 && 213 \end{align*}$$

Puzzles de Coppersmith-Winograd

Um quebra-cabeça de Coppersmith-Winograd (CWP) de comprimento e largura k consiste em um subconjunto S de { 1 , 2 , 3 } k de tamanho n no qual as "peças" são únicas - para quaisquer dois a ≠ b ∈ S e$n$$k$$S$$\{1,2,3\}^k$$n$$a \neq b \in S$ , { i ∈ [ k ] : um i = c } ≠ { i ∈ $c \in \{1,2,3\}$ (Eles apresentam um pouco diferente.)

$$\{ i \in [k] : a_i = c \} \neq \{ i \in [k] : b_i = c \}.$$

Cada USP é um CWP (como comentamos acima), portanto, a capacidade CWP satisfaz λ ≥ κ . Acima comentamos que$\lambda$$\lambda \geq \kappa$ . Fundidor e Winograd mostraram, utilizando um argumento sofisticado, que λ = 3 / 2 2 / 3 . Seu argumento foi simplificado por Strassen (veja ateoria da complexidade algébrica). Esboçamos uma prova simples abaixo.$\lambda \leq 3/2^{2/3}$$\lambda = 3/2^{2/3}$

$k$$V$$k/3$$1$$2$$3$$c \in \{1,2,3\}$$E_c$$a,b \in V$$\{ i \in [k] : a_i = c \} = \{ i \in [k] : b_i = c \}$$E = E_1 \cup E_2 \cup E_3$$G = (V,E)$$|V|^2/4|E|$$|V|/2|E|$

$$|V| = \binom{k}{k/3} \binom{2k/3}{k/3}, \quad |E| \leq 3|E_1| = \frac{3}{2}\binom{k}{k/3} \binom{2k/3}{k/3}^2.$$ $$\frac{|V|^2}{4|E|} = \frac{1}{6} \binom{k}{k/3} \Longrightarrow \lambda \geq \frac{3}{2^{2/3}}.$$

$S$

$S$$2^V$$\Pr[x \in S] = (|V|/2|E|)^{1-\epsilon}$$x,y,z \in V$$x$$y$$z$$w \in V$$x,y,z \in S$$w \in S$

$S$$V$$(x,y) \in E$$x,y$$(|V|^2/2|E|)^{1-\epsilon}$$T$$x,y,z \in T$$x$$y$$z$$w$$x,y,z,w \in S$$x,y,z$$S$