Существуют ли проблемы в CS, где эффективные алгоритмы не известны, несмотря на теоремы существования, доказывающие, что такие эффективные алгоритмы должны существовать? Как называются эти проблемы? Где я могу узнать...
В статье Томаса Дж. Шефера « Сложность проблем с удовлетворенностью» автор упомянул, что This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the relational complexity...
Тензор является обобщение векторов и матриц на более высокие размеры и ранг тензора также обобщает ранг матрицы. А именно, ранг тензора является минимальным числом ранга один тензоров этой суммы . Вектор и матрица являются тензорами степени 1 и 2 соответственно.TTTTTTT Элементы в происходят из поля...
Кто-нибудь знает ссылки, в которых четко прописана связь между алгоритмом объединения и гауссовым исключением? Меня особенно интересует связь между треугольными заменами и LU-разложениями. Уэйн Снайдер и Джин Галлиер упоминают эту аналогию в своей статье « Возвращение к объединению высшего порядка:...
При разработке алгоритмов аппроксимации иногда решают полуопределенную программу с последующим шагом округления. Часто используемый пример, иллюстрирующий это, - Max-Cut. (См., Например, Алгоритмы аппроксимации Vijay Vazirani.) Существуют ли хорошие образовательные источники или обзоры, выходящие...
Я ищу ссылку на следующий результат: Добавление двух целых чисел в факторизованном представлении так же сложно, как и деление двух целых чисел в обычном двоичном представлении. (Я уверен, что это там, потому что это то, что я когда-то задавался вопросом, а затем был взволнован, когда я наконец...
Пусть G=(V,E)G=(V,E)G=(V,E) - граф. Для вершины x∈Vx∈Vx\in V , определим N(x)N(x)N(x) , чтобы быть (открытая) окрестность xxx в GGG . То есть N(x)={y∈V|{x,y}∈E}N(x)={y∈V|{x,y}∈E}N(x)=\{y\in V \,\vert\, \{x,y\}\in E\} . Определим две вершиныu,vu,vu,v вGGG какдвойники,еслиuuu иvvv имеют одинаковый...
Интересно, есть ли основания полагать, что или верить, что N L ≠ L ?NL = LNL=LNL=LNL ≠ LNL≠LNL\neq L Известно, что . Литература по derandomization из R L является довольно убедительным , что R L = L . Кто-нибудь знает о каких-то статьях или идеях, убеждая, что N L ≠ L ?NL ⊂ L2NL⊂L2NL \subset L^2R...
Существует ли хороший опрос, в котором сравниваются различные экстракторы, концентраторы и суперконцентраторы и излагаются лучшие методы с точки зрения компромисса между случайностью, временем и пространством?...
Я видел (и слышал), что он утверждал, что безопасно добавить классическую аксиому исключенного среднего к Coq, но я не могу найти документ, подтверждающий это утверждение. Статьи, которые я вижу в списке в вики Coq о исключенной середине, показывают несоответствие с нечетким множеством....
Я ищу языки, которые "вероятно, не являются контекстно-свободными", но мы не можем (не) доказать это, используя известные стандартные методы. Есть недавний опрос на предмет или открытый проблемный раздел от недавней конференции? Вероятно, не так много языков, которые не известны как CF, поэтому,...
Есть много мест, где числа ππ\pi и (1+5–√)/2(1+5)/2(1+\sqrt5)/2появляются. Мне любопытно узнать об алгоритмах, время выполнения которых содержит золотое сечение илиππ\piв показателе...
N CNC\mathsf{NC} отражает идею эффективного распараллеливания, и одна из его интерпретаций - это проблемы, которые разрешимы во времени с использованием параллельных процессоров для некоторых констант , . У меня вопрос, есть ли аналогичный класс сложности, где время равно а число процессоров - ....
Я столкнулся со следующим результатом во время моего исследования. limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1 где m=ω(n−−√)m=ω(n)m=\omega(\sqrt n) и a1,⋯,ama1,⋯,ama_1,\cdots,a_m...
Когда я преподаю границы хвоста, я использую обычную прогрессию: Если ваш тренд положительный, вы можете применить неравенство Маркова Если у вас есть независимость, а также ограниченная дисперсия, вы можете применить неравенство Чебышева Если каждый независимый rv также имеет все ограниченные...
Рассмотрим следующие рассуждения: Пусть обозначим сложность Колмогорова из строки . Теорема Чайтена о неполноте гласит, чтохК( х )K(x)K(x)Иксxx для любой последовательной и достаточно сильной формальной системы , существует постоянную (зависящую только от формальной системы и ее языка), что для...
Недавно я работал над проблемой вычисления приблизительной суммы списка отсортированных неотрицательных чисел. При любом фиксированном , с Схема времени аппроксимации была получена таким образом, что она дает -аппроксимация на сумму. Документ размещен по адресу http://arxiv.org/abs/1112.0520 ,...
Фон: Пусть две вершины неориентированного графа . Множество вершин является -сепаратором, если и принадлежат различным связным компонентам . Если собственное подмножество -сепаратора является -сепаратором, то является минимальным -сепаратором. Множество вершин является (минимальным) разделителем,...
(Это продолжение этого вопроса и его ответа .) У меня есть следующая полностью унимодулярная (TU) целочисленная линейная программа (ILP). Здесь - все натуральные числа, заданные как часть входных данных. Указанное подмножество переменных x i j устанавливается в ноль, а остальные могут принимать...
Дополнение цепь представляет собой последовательность положительных целых чисел , где х 1 = 1 , и каждый индекс я ≥ 2 , мы имеем й я = х J + х K для некоторых индексов 1 ≤ J , к < я . Длина прибавления цепи п ; мишень из капельной цепи х( х1, х2, … , ХN)(x1,x2,…,xn)(x_1, x_2, \dots, x_n)Икс1=...