Проводились ли какие-либо исследования, чтобы определить, может ли человеческий интеллект превзойти алгоритмы (т. Е. Проверить, применима ли теорема об отсутствии бесплатного обеда к человеческому интеллекту)? В том же ключе, кто-нибудь разработал технический метод, чтобы воспользоваться...
Извините, если я ошибаюсь с местом, чтобы задать вопрос (может быть, я должен пойти на stackoverflow.com/mathoverflow.net?). Интересно, есть ли доказательство того, что при оценке расширенного евклидова алгоритма коэффициенты Безу ( т. Е. S и t в тождестве как + bt = gcd ( a , b )) не будут...
Пусть - ациклический ориентированный граф, такой что out-степень любой вершины равна O ( log | V | ) . Для каждой вершины G мы можем подсчитать количество достижимых вершин, просто запустив dfs из каждой вершины, и это займет O ( | V | | E | ) время. Есть ли лучший способ решить эту...
Что мешает сделать решатели SAT конкурентоспособными с помощью специализированных графовых алгоритмов? Другими словами, возможно ли ожидать SAT-решателей, которые могут заменить роль разработчика алгоритма, т. Е. Иметь возможность автоматически распознавать структуру проблемы и затем решать ее так...
Существует ли класс алгоритмов хеширования, теоретический или практический, такой, чтобы алгоритм в классе можно было считать «рефлексивным» согласно определению, данному ниже: hash1 = algo1 ("текст ввода 1") hash1 = algo1 («входной текст 1» + hash1) Оператор + может быть конкатенацией или любой...
Мерлин, имеющий неограниченные вычислительные ресурсы, хочет убедить Артура, что для с и Простое вычисление этой суммы (модульное возведение в степень и сложение) занимает время с умножением на основе БПФ. * Но Артур может выполнять только операций.m|∑p≤N, p primepkm|∑p≤N, p primepkm|\sum_{p\le N,\...
Я был бы очень заинтересован ссылками на теорию субмодулярных функций (от основ до продвинутых). В частности, я изучаю приближения к сложным задачам оптимизации и хочу развить свои основы субмодулярных функций, поскольку они имеют отношение к задачам оптимизации, которые я изучал. Заранее...
Учитывая взвешенный неориентированный граф с m = o ( n2)m=o(n2)m = o(n^2) ребрами, я хотел бы вычислить расстояния приближения меньше 2 между любой данной парой вершин. Конечно, я хотел бы использовать субквадратичное пространство и время сублинейного запроса. Мне известен результат Цвика, который...
Пусть - последовательность целых чисел, где каждый . Для , пусть, - й момент частоты определяется какa j ∈ { 1 , 2 , … , n } i ∈ { 1 , 2 , … , n } m i = | { j : a j = i } | Кa1,a2,…,ama1,a2,…,ama_1, a_2,\dotsc, a_maj∈{1,2,…,n}aj∈{1,2,…,n}a_j \in \{1,2,\dotsc,n\}i∈{1,2,…,n}i∈{1,2,…,n}i \in...
Алгоритмы аппроксимации могут давать результат до некоторого постоянного фактора. Это немного менее удовлетворительно, чем точные алгоритмы. Однако постоянные факторы игнорируются во временной сложности. Поэтому мне интересно, возможен ли или был использован следующий прием для решения некоторой...
Я знаком с алгоритмом градиентного спуска, который может найти локальный минимум (максимум) данной функции. Есть ли какая-либо модификация градиентного спуска, которая позволяет найти абсолютный минимум (максимум), где функция имеет несколько локальных экстремумов? Существуют ли общие методы, как...
Пусть вещественная матрица ( ) обладает тем свойством, что любой набор из столбцов имеет полный ранг.k × nК×Nk\times nk ≤ nК≤Nk\le nAA{\bf A}ККk В: Существует ли эффективный способ детерминированного поиска вектора такой, что расширенная матрица сохраняет то же свойство, что и : любые столбцов...
Согласно книге «Топологическая теория графов» Гросса и Такера, учитывая клеточное вложение графа на поверхность (под «поверхностью» я подразумеваю здесь сферу с некоторыми ручками , а ниже S n относится к сфере с ровно n ручками), можно определить двойной мультиграф, рассматривая грани исходного...
Для данного графа со взвешенными ребрами, как мы можем найти отрицательный цикл, который содержит хотя бы одну вершину в данном наборе вершин ? Спасибо.{V1,V2,…,Vk}{В1,В2,...,ВК}\{V_1, V_2, \ldots,...
Рассмотрим наборов значений (представленных в виде отсортированных массивов без дубликатов и с известным размером (т. Е. Размер можно получить за O (1)). Значения можно проверить на равенство за O (1). Я хочу чтобы получить набор значений, которые присутствуют по меньшей мере в k различных наборах...
Я ищу способ генерации графов, чтобы было известно оптимальное покрытие вершин. Нет ограничений на количество узлов или ребер, только то, что граф полностью связен. идея состоит в том, чтобы создать граф, который не легко найти оптимальное покрытие вершин, чтобы иметь возможность тестировать...
У меня есть несколько миллионов 32-битных значений. Для каждого значения я хочу найти все другие значения в пределах расстояния Хэмминга, равного 5. В наивном подходе это требует сравнений, которых я хочу избежать.O ( N2)O(N2)O(N^2) Я понял, что если я просто обработал эти 32-битные значения как...
Была ли эта проблема изучена раньше? Учитывая метрический неориентированный граф G (длины ребер удовлетворяют неравенству треугольника), найдите множество S вершин, таких что MST (G [S]) максимизировано, где MST (G [S]) - минимальное остовное дерево подграфа, индуцированное С. Была ли эта проблема...
Я ищу эффективный алгоритм для решения проблемы: Входные данные : положительное целое число 3n3n3^n (сохраняется в виде битов) для некоторого целого числа n≥0n≥0n \geq 0 . Вывод : число nnn . Вопрос : Можем ли мы вычислить nnn из битов 3n3n3^n за O(n)O(n)O(n) времени? Это теоретический вопрос,...
У меня есть трудности в понимании последних шагов алгоритма AHSP. Пусть абелева группа и е функция , которая скрывает подгруппу H . Пусть G * представляет двойную группу G .GGGfffHHHG∗G∗G^*GGG Вот шаги алгоритма Сначала подготовь государство, .I=1|G|∑g∈G|g⟩|0⟩I=1|G|∑g∈G|g⟩|0⟩\qquad \displaystyle...