Конструкции лучше случайных.

10

Меня интересуют примеры конструкций в теории сложности, которые лучше случайных.

Я знаю только один пример такой конструкции в области кодов, исправляющих ошибки. Коды алгебраической геометрии лучше в некотором диапазоне параметров, чем случайные коды.

Можно легко построить такие искусственные примеры. Меня интересуют примеры, такие как коды алгебраической геометрии, где легко создать случайную конструкцию и не очевидно, как это сделать лучше.

клим
источник
7
Этот вопрос ужасно расплывчатый. Пожалуйста, по крайней мере, укажите, о какой области вы говорите.
Дэйв Кларк,
Я добавил тег [большой список] и отметил его для внимания модератора, попросив его сделать этот вопрос вики-сообществом.
Цуёси Ито
4
Мне нравится вопрос, но мы можем как-то ограничить сферу. Понятно, что такие вещи, как конечные группы, проективные плоскости и т. Д., Если вы правильно их параметризуете (например, количество триплетов, нарушающих ассоциативность), будут иметь гораздо лучшие параметры, чем случайные конструкции.
Питер Шор
Я согласен, что вопрос неясен. Я не как ограничить сферу. Любые предложения приветствуются. Меня интересуют интересные примеры. Например, когда долгое время случайная конструкция была лучшей, и чтобы ее победить, нужны нетривиальные идеи.
Клим
@ Дэйв, не уверен, что это должен быть тег CW или [большой список], если вопрос неопределенный, мы должны попросить OP прояснить его, обратите внимание, что CW необратим. ИМХО, такой вопрос может быть изменен таким образом, что он должен быть вопросом большого списка.
Каве

Ответы:

11

Рамануджанские графы имеют второе собственное значение (с степенью графа), тогда как случайные графы достигают только whp На самом деле, в общем случае мы имеем , причем слагаемое, идущее к с сохраняемым постоянным (как число вершин ), поэтому в некотором смысле они являются оптимальными. Dλ22λ22D1DDλ22λ22D1D+o(1)o(1)0DNλ22D1Do(1)o(1)0DN

alpoge
источник
10

Существует конструкция Беренда большого подмножества которое не содержит трех элементов в арифметической прогрессии (сокращенно 3AP-free). Случайное подмножество размером , скажем, будет содержать множество арифметических прогрессий длины-3, но Беренд создаст набор без 3AP размера .{ 1 , , N } N 0,9 N 1 - o ( 1 ){1,,N}{1,,N}N0.9N1o(1)

Лука Тревизан
источник
6

Возможно, это не совсем то, что вы ищете, но Джефф Лагариас и я (позже улучшенный Макки) придумали мозаичные кубы пространств больших размеров, которые являются контрпримерами к гипотезе Келлера , то есть мозаичные элементы измерений с единичными кубами, где нет двух кубы встречаются в полном ( ) -мерном лице. Кажется маловероятным, что случайные наклоны дадут контрпримеры.n - 1nn1

Питер Шор
источник
5

Как правило, случайные конструкции и жадные конструкции достигают одинаковых границ (например, коды с исправлением ошибок). Однажды я услышал выступление Ловаша, в котором он сказал, что жадные и случайные выборы по сути одинаковы. Итак, любая конструкция, которая побеждает жадную конструкцию, должна дать ответ на ваш вопрос. В качестве быстрого примера, конструкции, которые достигают способности графов Спернера, относятся к этому виду. Как сказал Питер Шор, примеров экстремальной комбинаторики действительно много.

Уго
источник