Емкость Уникально Решаемой Головоломки (USP)

13

В своей основополагающей работе Теоретико-групповые алгоритмы для умножения матриц Кон, Кляйнберг, Сегеди и Уманс вводят концепцию однозначно решаемой головоломки (определено ниже) и емкость USP. Они утверждают, что Копперсмит и Виноград, в своих собственных новаторских работах по умножению матриц с помощью арифметических прогрессий , «неявно» доказывают, что емкость USP составляет . Это утверждение повторяется в нескольких других местах (в том числе и здесь), но нигде нет объяснения. Ниже мое собственное понимание того, что доказывают Копперсмит и Виноград, и почему этого недостаточно.3/22/3

Правда ли, что пропускная способность USP составляет ? Если да, есть ли ссылка на доказательство?3/22/3

Уникально решаемые головоломки

Уникально разрешимая головоломка (USP) длиной и шириной состоит из подмножества размера , которое мы также рассматриваем как три набора из «кусочков» (соответствующих места, где векторы равны , места, где они равны , и места, где они равны ), удовлетворяющие следующему свойству. Предположим, мы расположили все фигуры в строках. Тогда должен быть уникальный способ поместить другие части, по одному каждого типа в каждую строку, чтобы они «подходили».nk{1,2,3}knn1231n

Пусть - максимальная длина USP ширины . Емкость USP , является В USP каждая из частей должна быть уникальной - это означает, что никакие две строки не содержат символ в одинаковых местах. Это показывает (после короткого спора), что и т. д. ,N(k)k

κ=supkN(k)1/k.
c{1,2,3}
N(k)a+b+c=kmin{(ka),(kb),(kc)}(k+22)(kk/3),
κ3/22/3

Пример (USP длины и ширины ): Не пример длины и ширины , где - и части могут быть расположены двумя различными способами: 44

1111213112132233
3323
123132231321312213

Игры пазлы Медник-Виноград

Головоломка Копперсмита-Винограда (CWP) длиной и шириной состоит из подмножества размером размера в котором «кусочки» уникальны - для любых двух и , (Они представляют это несколько иначе.)nkS{1,2,3}knabSc{1,2,3}

{i[k]:ai=c}{i[k]:bi=c}.

Каждый USP - это CWP (как мы прокомментировали выше), поэтому емкость CWP удовлетворяет . Выше мы отметили, что . Копперсмит и Виноград показали, используя сложный аргумент, что . Их аргумент был упрощен Штрассеном (см. Теорию алгебраической сложности ). Мы нарисуем простое доказательство ниже.λλκλ3/22/3λ=3/22/3

Для заданного пусть состоит из всех векторов, содержащих каждый из с, с, с. Для пусть состоит из всех пар таких что , и положить . Каждое независимое множество в графе является CWP. Хорошо известно, что каждый граф имеет независимый набор размеров(доказательство: выберите каждую вершину с вероятностью и удалите одну вершину из каждого оставшегося ребра). В нашем случае kVk/3123c{1,2,3}Eca,bV{i[k]:ai=c}={i[k]:bi=c}E=E1E2E3G=(V,E)|V|2/4|E||V|/2|E|

|V|=(kk/3)(2k/3k/3),|E|3|E1|=32(kk/3)(2k/3k/3)2.
Следовательно,
|V|24|E|=16(kk/3)λ322/3.
Юваль Фильмус
источник
Интересно, но есть ли здесь вопрос, или это всего лишь утверждение о недостатке в литературе?
Дэвид Эппштейн
4
Вопрос в том, действительно ли пропускная способность УТП составляет , и если да, то где можно найти доказательства. 3/22/3
Юваль Фильмус

Ответы:

7

Как и многие другие вопросы, ответ на этот вопрос можно найти в диссертации Стозерса. Местный USP является НВП , в котором единственный способ , в котором 1-часть, 2- х частей и 3- х частей может поместиться вместе , если их объединение в . Ясно, что местная USP - это USP, и конструкция из [CKSU] показывает, что емкость USP достигается местными USP (мы собираемся показать это конструктивно).S

Копперсмит и Виноград строят почти 2-х независимое распределение на 2 V со следующими двумя свойствами: (1) Pr [ x S ] = ( | V | / 2 | E | ) 1 - ϵ , (2) Для любого x , y , z V такой, что 1-кусок x , 2-фрагмент y и 3-кусок z вместе образуют вектор w V : еслиS2VPr[xS]=(|V|/2|E|)1ϵx,y,zVxyzwV , то W S .x,y,zSwS

Мы выбираем случайное подмножество из V в соответствии с распределением, и для каждого ребра ( x , y ) E удаляем обе вершины x , y . Ожидаемое число вершин остались примерно ( | В | 2 / 2 | Е | ) 1 - ε . Результирующий набор T является локальным USP: если есть x , y , z T, в котором 1-кусок xSV(x,y)Ex,y(|V|2/2|E|)1ϵTx,y,zTx, 2-кусок и 3-кусок г посадки, образуя часть ш , то х , у , г , ш S , и поэтому все х , у , г удаляются из S .yzwx,y,z,wSx,y,zS

Юваль Фильмус
источник