Меня интересуют примеры конструкций в теории сложности, которые лучше случайных.
Я знаю только один пример такой конструкции в области кодов, исправляющих ошибки. Коды алгебраической геометрии лучше в некотором диапазоне параметров, чем случайные коды.
Можно легко построить такие искусственные примеры. Меня интересуют примеры, такие как коды алгебраической геометрии, где легко создать случайную конструкцию и не очевидно, как это сделать лучше.
Ответы:
Рамануджанские графы имеют второе собственное значение (с степенью графа), тогда как случайные графы достигают только whp На самом деле, в общем случае мы имеем , причем слагаемое, идущее к с сохраняемым постоянным (как число вершин ), поэтому в некотором смысле они являются оптимальными. Dλ2≤2 √λ2≤2D−1√D D λ2≥2 √λ2≤2D−1√D+o(1) o(1)0DN→∞λ2≥2D−1√D−o(1) o(1) 0 D N→∞
источник
Существует конструкция Беренда большого подмножества которое не содержит трех элементов в арифметической прогрессии (сокращенно 3AP-free). Случайное подмножество размером , скажем, будет содержать множество арифметических прогрессий длины-3, но Беренд создаст набор без 3AP размера .{ 1 , … , N } N 0,9 N 1 - o ( 1 ){1,…,N} {1,…,N} N0.9 N1−o(1)
источник
Возможно, это не совсем то, что вы ищете, но Джефф Лагариас и я (позже улучшенный Макки) придумали мозаичные кубы пространств больших размеров, которые являются контрпримерами к гипотезе Келлера , то есть мозаичные элементы измерений с единичными кубами, где нет двух кубы встречаются в полном ( ) -мерном лице. Кажется маловероятным, что случайные наклоны дадут контрпримеры.n - 1n n−1
источник
Как правило, случайные конструкции и жадные конструкции достигают одинаковых границ (например, коды с исправлением ошибок). Однажды я услышал выступление Ловаша, в котором он сказал, что жадные и случайные выборы по сути одинаковы. Итак, любая конструкция, которая побеждает жадную конструкцию, должна дать ответ на ваш вопрос. В качестве быстрого примера, конструкции, которые достигают способности графов Спернера, относятся к этому виду. Как сказал Питер Шор, примеров экстремальной комбинаторики действительно много.
источник