Задача суммы квадратных корней задает для заданных двух последовательностей a1,a2,…,ana1,a2,…,ana_1, a_2, \dots, a_n и b1,b2,…,bnb1,b2,…,bnb_1, b_2, \dots, b_n натуральных чисел, является ли сумма ∑iai−−√∑iai\sum_i \sqrt{a_i} меньше, равно или больше суммы . Статус сложности этой проблемы открыт;...
Эта проблема вдохновлена этим вопросом МО , который мне показался очень интересным. Какая самая старая открытая проблема в TCS? Очевидно, что этот вопрос нуждается в уточнении. Во-первых, что такое TCS? Я думаю, что существование нечетных совершенных чисел не TCS. Я бы сказал, что десятой проблемой...
Это не технический вопрос, но, безусловно, актуальный для сообщества TCS. Если считается неуместным, не стесняйтесь закрыть. Сложность зоопарка веб - страницы (http://qwiki.stanford.edu/index.php/Complexity_Zoo), безусловно , был большой сервис для сообщества ТКС на протяжении многих лет....
Мне любопытно, есть ли способ хранить хэш из нескольких множеств целых чисел, который в идеале имеет следующие свойства: Использует пространство O (1) Его можно обновить, чтобы отразить вставку или удаление за время O (1). Две идентичные коллекции (т. Е. Коллекции, имеющие одинаковые элементы с...
Во введении и объяснении P и NP классы сложности часто даются через машину Тьюринга. Одной из моделей вычислений является лямбда-исчисление. Я понимаю, что все модели вычислений эквивалентны (и если мы можем ввести что-либо в терминах машины Тьюринга, мы можем представить это в терминах любой...
В общем, мы знаем, что сложность проверки того, принимает ли функция определенное значение на данном входе, проще, чем оценка функции на этом входе. Например: Оценка перманента неотрицательной целочисленной матрицы является # P-сложной, но при этом указывается, является ли такой перманент нулевым...
Предположим, что соавторы из двух или более различных учреждений пишут бумагу в латексе и хотели бы добиться большего успеха, чем неоднократно отправлять черновики по электронной почте взад и вперед. Они понимают, что могут бесплатно открыть учетную запись Dropbox, поделиться паролем и...
Учитывая новую проблему в , истинная сложность которой находится где-то между и являющейся NP-полной, я знаю два метода, которые можно использовать, чтобы доказать, что решить эту проблему сложно:NPNP\mathsf{NP}PP\mathsf{P} Покажите, что задача является GI-полной (GI = Изоморфизм графов) Покажите,...
Какова верхняя граница симплексного алгоритма для поиска решения линейной программы? Как мне найти доказательства для такого случая? Кажется, что наихудший случай - посещение каждой вершины, то есть . Однако на практике симплексный алгоритм будет работать значительно быстрее, чем этот, для более...
Спросите даже кого-то, имеющего опыт работы в области компьютерных наук, что такое регулярное выражение, и ответ, вероятно, выйдет за пределы возможности быть в пределах досягаемости конечного автомата. Например, «регулярное выражение» /^1?$|^(11+?)\1+$/ созданная известной личностью Perl Абигейл...
Предыстория: мотивация этого вопроса двоякая. Во-первых, я хотел бы получить некоторые неопровержимые факты, чтобы лучше понять текущие конференции и дебаты в журналах . Во-вторых, если бы эта информация была где-то доступна, я мог бы принять более обоснованное решение при представлении документов...
Важное применение теоремы PCP состоит в том, что она дает результаты типа «твердость приближения». В некоторых относительно более простых случаях такую твердость можно доказать без PCP. Есть ли, однако, какой-либо случай, когда твердость результата аппроксимации была сначала доказана с...
Мы знаем, что экспоненциальная функция над натуральными числами не вычисляется за полиномиальное время, поскольку размер выходных данных не ограничен полиномиально по размеру входных данных.ехр( х , у) = хYехр(Икс,Y)знак равноИксY\exp(x,y) = x^y Является ли это основной причиной сложности...
Этот вопрос предназначен для людей, которые задают задачи: учителей, ассистентов студентов, репетиторов и т. Д. Это случалось со мной несколько раз за всю мою 12-летнюю карьеру профессора: я поспешно выдвинул некоторую проблему из текста, думая, что «это выглядит хорошо». Потом понял, что не могу...
Я ищу источник огромных наборов данных для проверки реализации алгоритма графа. Просьба также предоставить некоторую информацию о типе / распределении (например, направленных / ненаправленных, простых / не простых, взвешенных / невзвешенных) графиков в источнике, если они...
Решить, существует ли равновесие по Нэшу, легко (это всегда так); однако, на самом деле найти его, как полагают, сложно (это PPAD-Complete). Каковы другие примеры проблем, когда версия решения проста, но поисковая версия относительно сложна (по сравнению с версией решения)? Я был бы особенно...
В настоящее время я начинаю учиться в университете, и у нас есть много возможностей начать исследования. До того, как найти этот сайт, я не собирался идти по этому пути [я хотел работать с ИИ, возможно, разработчиком игр], но теперь я могу [или мне нужно] сделать выбор. Можете ли вы убедить меня...
Предполагается, что случайность не расширяет возможности алгоритмов полиномиального времени, то есть предполагается, что будет выполняться. С другой стороны, случайность, по-видимому, оказывает совершенно иное влияние на сокращение полиномиального времени . По хорошо известным результатам Valiant и...
Задача состоит в том, чтобы вычислить многочлен . Предположим, что все коэффициенты вписываются в машинное слово, т. Е. Ими можно манипулировать в единицу времени.( а1х + б1) × ⋯ × ( аNх + бN)(a1Икс+б1)×⋯×(aNИкс+бN)(a_1 x + b_1) \times \cdots \times (a_n x + b_n) Вы можете сделать раз, применяя БПФ...
Пусть AAA будет фиксированным положительным целым числом размером nnn бит. Разрешается предварительно обрабатывать это целое число соответствующим образом. Учитывая другое положительное целое число BBB размером mmm битов, какова сложность умножения ABABAB ? Обратите внимание, что у нас уже есть...