Этот вопрос перенесен из Биржи стеков информатики, потому что на него можно ответить в Теоретической бирже информатики. Мигрировал 3 года назад . В научной статье 2016 года « Реализация масштабируемого алгоритма Шора » [ 1 ] авторы учитывают 15 с только 5 кубитами, что меньше «требуемых» 8 кубитов...
Давайте посмотрим на будущее через 30 лет. Давайте будем оптимистичными и предположим, что области, связанные с машинным обучением, продолжают развиваться так же быстро, как мы видели за последние 10 лет. Это было бы здорово, но какова будет роль традиционной алгоритмики в таком будущем? Здесь под...
Я фиксируем регулярный язык на алфавите , и я считаю следующую проблему , которую я называю письмо планирования для L . Неофициально, ввод дает мне n букв и интервал для каждой буквы (то есть минимальную и максимальную позицию), и моя цель состоит в том, чтобы поместить каждую букву в ее интервал...
Прошло более года с момента его отвода и исправления в январе 2017 года. Есть ли новости? Если нет, то нормально ли это для проверки? Я ожидаю, что это привлечет много внимания. Кто-нибудь отметил, чтобы поддержать / сомневаться в квазиполиномиальном...
Недавнее и невероятно приятное доказательство гипотезы о чувствительности основано на явном * построении матрицы An∈{−1,0,1}2n×2nAn∈{−1,0,1}2n×2nA_n\in\{-1,0,1\}^{2^n\times 2^n} , определенной рекурсивно следующим образом: A1=(0110)A1=(0110)A_1 = \begin{pmatrix} 0&1\\1&0\end{pmatrix} и, для, В...
Точная формулировка названия принадлежит Ананду Кулькарни (который предложил создать этот сайт). Этот вопрос был задан в качестве примера вопроса, но мне безумно любопытно. Я очень мало знаю об алгебраической геометрии, и на самом деле у меня есть только беглое понимание студентами препятствий,...
При сжатии считывания цель состоит в том, чтобы найти схемы линейного сжатия для огромных входных сигналов, которые, как известно, имеют разреженное представление, чтобы входной сигнал мог быть эффективно восстановлен из сжатия («эскиз»). Более формально, стандартная установка состоит в том, что...
Скотт Ааронсон предложил интересную задачу : можем ли мы использовать суперкомпьютеры сегодня, чтобы помочь решить проблемы CS так же, как физики используют коллайдеры с крупными частицами? Более конкретно, мое предложение состоит в том, чтобы посвятить некоторые из мировых вычислительных мощностей...
Это похоже на « Алгоритмы из Книги ». Хотя сокращения также являются алгоритмами, я подумал, что сомнительно, что можно подумать о сокращении в ответ на вопрос об алгоритмах из книги. Отсюда отдельный запрос! Сокращения всех видов приветствуются. Я начну с действительно простого сокращения от...
Первоначальная теорема недетерминированной временной иерархии принадлежит Кук (ссылка на С. Кука, иерархия недетерминированной временной сложности , JCSS 7 343–353, 1973). Теорема утверждает, что для любых действительных чисел r1r1r_1 и r2r2r_2 , если 1≤r1<r21≤r1<r21 \le r_1 \lt r_2 то NTIME...
Вот несколько способов проанализировать время работы алгоритма: 1) Анализ наихудшего случая: время выполнения в худшем случае. 2) Анализ среднего случая: ожидаемое время работы на случайном экземпляре. 3) Амортизированный анализ: среднее время работы в наихудшей последовательности экземпляров. 4)...
Каковы основные ссылки? Существуют ли какие-либо хорошие высокоуровневые обзоры SGT и его приложений для CS в целом и машинного обучения более
В 1999 году Петра Шурман и Герхард Дж. Вёгингер опубликовали статью «Алгоритмы аппроксимации полиномиального времени для машинного планирования: десять открытых задач» . С тех пор, насколько мне известно, обзоры, которые касались бы одного и того же списка проблем, не появлялись. Таким образом,...
Я не совсем понимаю, почему почти все решатели SAT используют CNF вместо DNF. Мне кажется, что решение SAT проще с использованием DNF. В конце концов, вам просто нужно просмотреть набор импликантов и проверить, содержит ли один из них и переменную, и ее отрицание. Для CNF не существует такой...
Что известно о временной сложности следующей задачи, которую мы называем 3-MUL? Для заданного множества SSS из nnn целых чисел существуют ли такие элементы a,b,c∈Sa,b,c∈Sa,b,c\in S , что ab=cab=cab=c ? Эта проблема похожа на задачу 3-СУММ, которая спрашивает, существуют ли три элемента...
Питер Шор затронул интересный момент в связи с попыткой ответить на предыдущий вопрос о сложности решения кубика Рубика . Я опубликовал довольно наивную попытку показать, что она должна содержаться в NP. Как отметил Питер, в некоторых случаях мой подход не работает. Одним из возможных случаев...
Этот вопрос касается связи между нормальным умножением двоичных чисел и модулем умножения полиномов. Чтобы конкретизировать вопрос, я в идеале хотел бы знать, существует ли лучшее решение вопроса из Кнута тома. 2, 3-е издание, стр. 420, чем приведенное в книге. «Может ли умножение многочленов по...
В последние несколько месяцев я начал читать лекции о социальном выборе, теореме стрелы и связанных с ней результатах. Прочитав об исходных результатах, я спросил себя о том, что происходит с предпочтениями частичного порядка, ответ в статье Pini et al. : Агрегирование частично упорядоченных...
Я только что понял, что я предполагаю, что ответ на мой вопрос - «да», но у меня нет веской причины. Я предполагаю, что, возможно, существует сборщик мусора, который доказуемо вводит только замедление в худшем случае. Есть ли конкретная ссылка, которую я могу привести? В моем случае я работаю над...
Этот вопрос является продолжением вопроса об алгоритмах ДНК, заданного Аадитой Мехра . В комментариях Джо Фитцсиммонс сказал, частично: [T] Радиус системы должен масштабироваться пропорционально массе, чтобы избежать этого. Вычислительная мощность масштабируется максимально линейно по массе. Таким...