В адиабатических квантовых вычислениях (AQC) каждый кодирует решение задачи оптимизации в основном состоянии [проблемы] гамильтониана . Чтобы добраться до этого основного состояния, вы начинаете в легко охлаждаемом начальном (основном) состоянии с гамильтонианом и «отжигом» (адиабатически...
Меня интересуют модели случайных графов, которые похожи на графы реальных компьютерных сетей. Я не уверен, что общая хорошо изученная модель ( n вершин, каждое возможное ребро выбрано с вероятностью p ) подходит для изучения реальных компьютерных сетей (не так ли?).G ( n , p )G(n,p)G(n,p)Nnnпpp...
В распределенных вычислениях проблема консенсуса, по-видимому, является одной из центральных тем, которая привлекла интенсивные исследования. В частности, статья «Невозможность распределенного консенсуса с одним ошибочным процессом» была удостоена награды PODC за выдающуюся работу в 2001 году . Так...
Как известно, вычисление постоянной Чигера для графика , также известного как изопериметрическая постоянная (поскольку это, по сути, минимальное отношение площади / объема), является NP-полным. Вообще это приблизительно. Мне интересно узнать, известны ли точные полиномиальные алгоритмы для...
Я хотел бы знать, были ли предположения, которые давно не были доказаны в TCS, которые позже были подтверждены следствием другой теоремы, что, возможно, было легче доказать....
Меня интересует следующая проблема: учитывая множество X и подмножества X_1, ..., X_n из X, найдите раскраску элементов X с помощью k цветов, чтобы все элементы в каждом X_i были по-разному окрашены. Более конкретно, я смотрю на случай, когда все X_i имеют размер k. Известно ли это в литературе под...
Проблема: нам дают набор палочек, имеющих целую длину. Общая сумма их длин n (n + 1) / 2. Можем ли мы разбить их, чтобы получить палочки размером за полиномиальное время? 1 , 2 , … , n1,2,...,N{1,2,\ldots,n} Удивительно, но единственная ссылка, которую я нахожу для этой проблемы, - это древнее...
Я вижу много исследований в области гиперкомпьютеров в 1990-х, но в последние годы, кажется, мало работы по этой теме. Правда ли, что исследования в этой области прекратились? Если так, что может быть причинами этого? Была ли эта область убедительно показана...
Я хотел бы узнать о параметризованной сложности (как на алгоритмической стороне, так и на жесткости). Какие книги / конспекты лекций я могу прочитать на эту...
Проблема удовлетворенности является, конечно, фундаментальной проблемой в теоретической CS. Я играл с одной версией проблемы с бесконечным количеством переменных. \newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}} Базовая настройка. Пусть непустое и, возможно, бесконечное множество...
Каковы известные эффективные алгоритмы вычисления определителя целочисленной матрицы с коэффициентами в , кольца вычетов по модулю m . Число m может быть не простым, а составным (поэтому вычисления выполняются в кольце, а не в поле).ZмZм\mathbb{Z}_mммmммm Насколько я знаю (читайте ниже),...
Недавний подход к созданию децентрализованной онлайн-валюты под названием биткойн вызвал некоторый интерес. Цель состоит в том, чтобы иметь возможность переводить валюту без центрального органа и без двойных расходов или подделок. Их подход заключается в том, чтобы все узлы в сети пытались...
Предположим, что TTT - дерево постоянной степени, структура которого мы не знаем. Проблема состоит в том, чтобы вывести дерево , задавая запросы в форме: «Находится ли узел на пути от узла к узлу ?». Предположим, что на каждый запрос оракул может ответить в постоянное время. Мы знаем значение ,...
2 вопроса для вычислительных геометров или алгебраистов: Я только начинаю погружаться в вычислительную геометрию, и мне это нравится =) Я пытаюсь прочитать знаменитую статью Гибаса и Столфи под названием «Примитивы для манипулирования общими подразделениями и вычисления диаграмм Вороного» с целью...
Верно ли, что в полиномиальной иерархии существуют проблемы, разрешимые во времени (с помощью чередующейся машины Тьюринга на некотором уровне полиномиальной иерархии), которые не разрешимы в O ( n k - 1 ) на любом уровне полиномиальная иерархия? Другими словами - существует ли теорема временной...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
Работать напрямую со сложностью времени или нижними границами схемы страшно. Следовательно, мы разрабатываем такие инструменты, как сложность запросов (или сложность дерева решений), чтобы справиться с нижними границами. Поскольку каждый запрос занимает по крайней мере один блок-шаг, а вычисления...
Проблема остановки для машин Тьюринга, возможно, является каноническим неразрешимым множеством. Тем не менее, мы доказываем, что существует алгоритм, решающий почти все его экземпляры. Таким образом, проблема остановки является одной из растущих коллекций тех, кто демонстрирует феномен «черной...
XORification - это метод усложнения булевой функции или формулы путем замены каждой переменной на XOR k ≥ 2 различных переменных x 1 ⊕ … ⊕ x k . xxxk≥2k≥2k\geq 2x1⊕…⊕xkx1⊕…⊕xkx_1 \oplus \ldots \oplus x_k Мне известно об использовании этого метода для усложнения доказательства, главным образом для...
Существуют ли алгоритмы решения SAT, не основанные на DPLL? Или все алгоритмы, используемые решателями SAT, основаны на