Скотт Ааронсон предложил интересную задачу : можем ли мы использовать суперкомпьютеры сегодня, чтобы помочь решить проблемы CS так же, как физики используют коллайдеры с крупными частицами?
Более конкретно, мое предложение состоит в том, чтобы посвятить некоторые из мировых вычислительных мощностей тотальной попытке ответить на такие вопросы, как следующие: требует ли вычисление перманента матрицы 4 на 4 больше арифметических операций, чем вычисление его детерминанта?
Он приходит к выводу, что для этого потребуется ~ операций с плавающей запятой, что выходит за рамки наших текущих возможностей. Эти слайды доступны и также стоит прочитать.
Есть ли какой-либо приоритет для решения открытых задач TCS с помощью экспериментов с перебором?
Ответы:
В «Нахождении эффективных цепей с использованием SAT-решателей» Кожевников, Куликов и Ярославцев использовали SAT-решатели, чтобы найти лучшие схемы для вычисления функции .MO DК
Я использовал компьютеры, чтобы найти доказательства нижних границ пространства-времени, как описано здесь . Но это было возможно только потому, что я работал с чрезвычайно строгой системой доказательств.
Maverick Woo и я некоторое время работали над поиском «правильного» домена для проверки верхних / нижних границ схемы с помощью компьютеров. Мы надеялись, что мы можем разрешить против A C C 0 (или очень слабую версию) с использованием решателей SAT, но это выглядит все более и более маловероятным. (Надеюсь, Маверик не против, чтобы я сказал это ...)СС0 A CС0
Первая общая проблема с использованием поиска методом грубой силы для доказательства нетривиальных нижних границ состоит в том, что это занимает слишком много времени, даже на очень быстром компьютере. Альтернатива состоит в том, чтобы попытаться использовать решатели SAT, решатели QBF или другие сложные инструменты оптимизации, но, похоже, их недостаточно, чтобы компенсировать огромные масштабы пространства поиска. Проблемы синтеза цепей являются одними из самых сложных практических примеров, которые можно найти.
Вторая общая проблема заключается в том, что «доказательство» полученной нижней границы (полученной путем поиска методом грубой силы и ничего не находящего) будет безумно длинным и, по-видимому, не даст понимания (кроме факта, что нижняя граница верна). Таким образом, большая проблема для «экспериментальной теории сложности» состоит в том, чтобы найти интересные вопросы нижней границы, для которых возможное «доказательство» нижней границы достаточно короткое, чтобы его можно было проверить, и достаточно интересное, чтобы привести к дальнейшему пониманию.
источник
Многие из лучших оценок в теории Рамсея осуществляются путем грубого форсирования множества умно сгенерированных (неизоморфных) графов. Прогресс в теории Рамсея обычно колеблется между математическим и вычислительным прогрессом в решении проблемы.
В общем, компьютерная грубая сила часто используется, чтобы получить некоторые доказательства для предположений, когда нет никаких доказательств, как известно. Например, гипотеза Гольдбаха и гипотеза Римана были проверены с помощью компьютерного поиска до очень больших чисел.
источник