Kapasitas Uniquely Solvable Puzzle (USP)

Dalam makalah seminal mereka, algoritma Group-theoretic untuk perkalian matriks , Cohn, Kleinberg, Szegedy dan Umans memperkenalkan konsep puzzle yang dapat dipecahkan secara unik (didefinisikan di bawah) dan kapasitas USP. Mereka mengklaim bahwa Coppersmith dan Winograd, di sendiri kertas terobosan mereka Matrix perkalian melalui deret aritmetika , "implisit" membuktikan bahwa kapasitas USP adalah $3/2^{2/3}$ . Klaim ini diulangi di beberapa tempat lain (termasuk di sini pada sejarah), namun tidak ada penjelasan yang dapat ditemukan. Di bawah ini adalah pemahaman saya sendiri tentang apa yang Coppersmith dan Winograd buktikan, dan mengapa itu tidak cukup.

Apakah benar bahwa kapasitas USP adalah $3/2^{2/3}$ ? Jika demikian, apakah ada referensi untuk buktinya?

Teka-teki unik yang dapat dipecahkan

Teka-teki yang dapat dipecahkan secara unik (USP) dengan panjang $n$ dan lebar $k$ terdiri dari himpunan bagian $\{1,2,3\}^k$ dengan ukuran $n$ , yang juga kita anggap sebagai tiga koleksi $n$ "keping" (sesuai dengan tempat di mana vektor adalah $1$ , tempat di mana mereka adalah $2$ , dan tempat-tempat di mana mereka berada $3$ ), memuaskan properti berikut. Misalkan kita mengatur semua $1$ buah dalam $n$ baris. Maka harus ada cara unik untuk meletakkan potongan-potongan lainnya, satu dari setiap jenis di setiap baris, sehingga mereka "pas".

Biarkan menjadi panjang maksimum USP lebar k . The kapasitas USP adalah κ = sup k N $N(k)$$k$ Dalam USP, masing-masing bagian harus unik - artinya tidak ada dua garis yang mengandung simbol c ∈ { 1 , 2 , 3 } di tempat yang persis sama. Ini menunjukkan (setelah argumen singkat) bahwa N ( k ) ≤ Σ a + b + c

$$\kappa = \sup_k N(k)^{1/k}.$$ $c \in \{1,2,3\}$ danκ≤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}$

Contoh (USP panjang dan lebar 4 ): 1111 2131 1213 2233 Non-contoh panjang 3 dan lebar 3 , di mana potongan 2 - dan 3 dapat disusun dengan dua cara berbeda: $4$$4$

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

Teka-teki Coppersmith-Winograd

Teka-teki Coppersmith-Winograd (CWP) dengan panjang dan lebar k terdiri dari subset S dari { 1 , 2 , 3 } k dengan ukuran n di mana "keping" itu unik - untuk dua a ≠ b ∈ S dan $n$$k$$S$$\{1,2,3\}^k$$n$$a \neq b \in S$ , { i ∈ [ k ] : a i = c } ≠ { i ∈ $c \in \{1,2,3\}$ (Mereka menyajikannya agak berbeda.)

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

Setiap USP adalah CWP (seperti yang kami komentari di atas), maka kapasitas CWP memenuhi λ ≥ κ . Di atas kita berkomentar bahwa λ ≤ 3 / 2 2 / 3 . Tembaga dan Winograd menunjukkan, menggunakan argumen yang canggih, yang λ = 3 / 2 2 / 3 . Argumen mereka disederhanakan oleh Strassen (lihat teori kompleksitas aljabar ). Kami membuat sketsa bukti sederhana di bawah ini.$\lambda$$\lambda \geq \kappa$$\lambda \leq 3/2^{2/3}$$\lambda = 3/2^{2/3}$

Diberikan , misalkan V terdiri dari semua vektor yang mengandung k / 3 masing-masing dari 1 s, 2 s, 3 s. Untuk c ∈ { 1 , 2 , 3 } , misalkan E c terdiri dari semua pasangan a , b ∈ V sehingga { i ∈ [ k ] : a i = c } = { i ∈ [ k ] $k$$V$$k/3$$1$$2$$3$$c \in \{1,2,3\}$$E_c$$a,b \in V$ , dan letakkan E = E 1 ∪ E 2 ∪ E 3 . Setiap set independen dalam grafik G = ( V , E ) adalah CWP. Sudah diketahui bahwa setiap grafik memiliki ukuran ukuran yang independen | V | 2 / 4 | E | (bukti: pilih setiap simpul dengan probabilitas | V | / 2 | E | , dan hapus satu simpul dari masing-masing tepi yang bertahan). Dalam kasus kami, $\{ 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|$ Oleh karena itu | V|

$$|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$

Coppersmith dan Winograd membangun distribusi independen hampir 2-bijaksana pada 2 V dengan dua properti berikut: (1) Pr [ x ∈ S ] = ( | V | / 2 | E | ) 1 - $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$ .