Pojemność jednoznacznie rozwiązanej układanki (USP)

W swoim kluczowym artykule Teoretyczne algorytmy grupowania macierzy Cohn, Kleinberg, Szegedy i Umans przedstawiają koncepcję unikatowej układanki (zdefiniowanej poniżej) i zdolności USP. Twierdzą oni, że Coppersmith i Winograd, w ich własnym papierze przełomowy Mnożenie macierzy poprzez ciąg arytmetyczny , „pośrednio” udowodnić, że zdolność USP jest $3/2^{2/3}$ . Twierdzenie to zostało powtórzone w kilku innych miejscach (w tym tutaj w cstheory), ale nigdzie nie ma wyjaśnienia. Poniżej moje własne rozumienie tego, co udowodnili Coppersmith i Winograd i dlaczego to nie wystarczy.

Czy to prawda, że pojemność USP jest $3/2^{2/3}$ ? Jeśli tak, czy istnieje odniesienie do dowodu?

Unikalne łamigłówki

Unikalnie rozwiązana łamigłówka (USP) o długości $n$ i szerokości $k$ składa się z podzbioru $\{1,2,3\}^k$ o rozmiarze $n$ , który również traktujemy jako trzy kolekcje $n$ „kawałków” (odpowiadające miejscom, w których wektory to $1$ , miejsca, w których są $2$ , i miejsca, w których są $3$ ), spełniające następującą właściwość. Załóżmy, że ułożyliśmy wszystkie $1$ części w $n$ liniach. Następnie musi istnieć unikalny sposób umieszczenia innych elementów, po jednym z każdego rodzaju w każdej linii, tak aby „pasowały”.

$N(k)$ $k$

κ = sup_{k} N (k)^{1 / k} .

$\kappa = \sup_k N(k)^{1/k}.$

c \in {1, 2, 3}

$c \in \{1,2,3\}$

N (k) \leq \sum_{a + b + c = k} min {(\binom{k}{a}), (\binom{k}{b}), (\binom{k}{c})} \leq (\binom{k + 2}{2}) (\binom{k}{k / 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},$

κ \leq 3 / 2^{2 / 3}

$\kappa \leq 3/2^{2/3}$

Przykład (USP o długości i szerokości ): Brak przykładu o długości i szerokości , gdzie - i - elementy można ułożyć na dwa różne sposoby: $4$ $4$

\begin{aligned} 1111 \\ 2131 \\ 1213 \\ 2233 \end{aligned}

$\begin{align*} 1111 \\ 2131 \\ 1213 \\ 2233 \end{align*}$

3

$3$

3

$3$

2

$2$

3

$3$

\begin{aligned} 123 & 132 \\ 231 & 321 \\ 312 & 213 \end{aligned}

$\begin{align*} 123 && 132 \\ 231 && 321 \\ 312 && 213 \end{align*}$

Zagadki Coppersmith-Winograd

Coppersmith Winograd-logiczna (CWP) o długości i szerokości składa się z podzbioru o o rozmiarach , w którym "fragmenty" są unikalne - dla dwóch i , (Prezentują to nieco inaczej.) $n$ $k$ $S$ $\{1,2,3\}^k$ $n$ $a \neq b \in S$ $c \in \{1,2,3\}$

{i \in [k] : a_{i} = c} \neq {i \in [k] : b_{i} = c} .

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

Każdy USP jest CWP (jak skomentowaliśmy powyżej), stąd pojemność CWP spełnia . Powyżej skomentowaliśmy, że . Coppersmith i Winograd wykazali, używając wyrafinowanego argumentu, że . Ich argumentacja została uproszczona przez Strassena (patrz teoria złożoności algebraicznej ). Poniżej przedstawiamy prosty dowód. $\lambda$ $\lambda \geq \kappa$ $\lambda \leq 3/2^{2/3}$ $\lambda = 3/2^{2/3}$

Biorąc pod uwagę , niech składać ze wszystkich wektorów zawierających z s, s, s. Dla , niech składać ze wszystkich par takich, że i wstaw . Każdy niezależny zestaw na wykresie jest CWP. Powszechnie wiadomo, że każdy wykres ma niezależny zestaw wielkości(dowód: wybierz każdy wierzchołek z prawdopodobieństwem i usuń jeden wierzchołek z każdej ocalałej krawędzi). W naszym przypadku, $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{2 k / 3}{k / 3}), | E | \leq 3 | E_{1} | = \frac{3}{2} (\binom{k}{k / 3}) {(\binom{2 k / 3}{k / 3})}^{2} .

$|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.$ Stąd

\frac{| V |^{2}}{4 | E |} = \frac{1}{6} (\binom{k}{k / 3}) ⟹ λ \geq \frac{3}{2^{2 / 3}} .

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

— Yuval Filmus
źródło

Ciekawe, ale czy jest tu pytanie, czy to tylko stwierdzenie wady w literaturze?

— David Eppstein

Pytanie brzmi, czy to prawda, że pojemność USP wynosi 3/2 , a jeśli tak, to gdzie można znaleźć dowód.

3 / 2^{2 / 3}

$3/2^{2/3}$

— Yuval Filmus

Podobnie jak wiele innych pytań, odpowiedź na to pytanie znajduje się w pracy doktora Stothersa. Lokalny USP jest CWP w których jedynym sposobem, w którym jeden jednoczęściowy 2 jednoczęściowy i 3 jednoczęściowy zmieści się razem, gdy ich suma jest . Najwyraźniej lokalny USP jest USP, a konstrukcja z [CKSU] pokazuje, że pojemność USP jest osiągana przez lokalnych USP (pokażemy to konstruktywnie). $S$

Coppersmith i Winograd konstruują prawie 2-mądry niezależny rozkład na z następującymi dwoma właściwościami: (1) , (2) Dla dowolnego tak, że 1 element , 2 element i 3 element razem tworzą wektor : jeśli następnie . $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$

Wybieramy losowego podzbioru o zgodnie z rozkładem, a każda krawędź usuwamy oba wierzchołki . Oczekiwana liczba pozostałych wierzchołków to w przybliżeniu . Wynikowy zestaw jest lokalnym USP: jeśli istnieją w którym 1-częściowy , 2-częściowy 3-częściowy pasuje, tworząc kawałek , to , a więc wszystkie są usuwane z . $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$

— Yuval Filmus
źródło