В статье Бен-Дор / Галеви [1] приводится еще одно доказательство того, что перманент является -завершенным. В более поздней части статьи они показывают цепочку сокращений то время как постоянное значение сохраняется вдоль цепи. Так как число постоянных назначений формулы 3SAT может быть получено из...
Я интересуюсь ранней историей опубликованных результатов о пространственно-временных компромиссах общего назначения. В частности, я хочу знать, кто первым описал следующий тип алгоритма для вычисления вычисления, имеющего произвольный граф потока данных с степенью O (1), используя пространство,...
Какова вычислительная сложность оптимизации различных функций над унитарной группой ?U( н )U(N)\mathcal{U}(n) Типичная задача, возникающая часто в квантовой теории информации, было бы максимизировать количество типа (или выше многочленов порядка в ) по всем унитарные матрицы . Является ли этот тип...
Ответ: не известно. Задаваемые вопросы являются естественными, открытыми и, по-видимому, сложными; сейчас вопрос вики сообщества. обзор Вопрос состоит в том, чтобы разделить языки, принадлежащие к классу сложности PPP - вместе с машинами Тьюринга (TM), которые принимают эти языки, - на два...
Какова наиболее известная сложность запроса алгоритма обучения Голдрайха-Левина? Лекционные заметки из блога Лука Тревисан в , леммы 3, утверждает его как . Это самый известный с точки зрения зависимости от п ? Буду особенно благодарен за ссылку на цитируемый источник!O ( 1 / ϵ4журнал nн...
Я ищу информацию о вычислительной сложности матричного умножения прямоугольных матриц. Википедия утверждает, что сложность умножения на составляет (умножение в школьных учебниках).A∈Rm×nA∈Rm×nA \in \mathbb{R}^{m \times n}B∈Rn×pB∈Rn×pB \in \mathbb{R}^{n \times p}O(mnp)O(mnp)O(mnp) У меня есть...
Я начинаю свою докторскую диссертацию этой осенью и планирую работать над теорией сложности для своей диссертации. Я составляю список важных работ, которые должен знать каждый теоретик сложности. Какие документы вы бы предложили человеку, как я? И, пожалуйста, кратко объясните, почему вы считаете...
Мой первый вопрос: известна ли интерактивная характеристика системы доказательств для всех классических классов сложности. Я бы назвал P, NP, PSPACE, EXP, NEXP, EXPSPACE рекурсивными и рекурсивно перечислимыми функциями классическими (среди прочих). В частности, известна ли интерактивная...
Результат 1: Теорема Линиала-Мансура-Нисана говорит о том, что вес Фурье функций, вычисленных по схемам сосредоточен на подмножествах малого размера с высокой вероятностью.AC0AC0\mathsf{AC}^0 Результат 2: вес Фурье у сконцентрирован на коэффициенте степени n .PARITYPARITY\mathsf{PARITY}nnn Вопрос:...
GI и проблема узлов являются проблемой определения структурной эквивалентности математических объектов. Есть ли какие-либо результаты установления связей между ними? Хорошие связи проблемы узлов со статистической физикой были изучены с помощью полиномов узлов , есть ли похожие результаты для ?G...
Какой класс сложности связан с исчерпывающими алгоритмами поиска? (если есть) Это NP или PSPACE? Существуют ли ограниченные модели вычислений, охватывающие класс алгоритмов исчерпывающего поиска, аналогичных моделям для жадного и динамического...
Принимая во внимание в качестве входных данных целое число и множество S наборов элементов { 1 , . , , , П } , что является сложность нахождения множество Т элементов { 1 , . , , , n } такой, что T имеет минимальную мощность и T не входит ни в один из множеств S ?nnnSSS{1,...,n}{1,...,n}\{1, ...,...
Из комментариев на один из моих вопросов о MathOverflow у меня возникает ощущение, что вопрос о GCD в vs. похож на вопрос о целочисленной факторизации в vs. .N CNС\mathsf{NC}пп\mathsf{P}пп\mathsf{P}Н ПNп\mathsf{NP} Существует ли что-то вроде алгоритма «квант » для GCD, поскольку существует алгоритм...
Долгое время я думал, что задача была NP-полной, если она (1) NP-сложная и (2) в NP. Однако в известной статье «Метод эллипсоидов и его последствия в комбинаторной оптимизации» авторы утверждают, что проблема дробного хроматического числа принадлежит NP и является NP-сложной, но пока неизвестно,...
Этот вопрос был задан Яном Паксом в списке рассылки « Основы математики» . Конечно, но из ответов на этот вопрос я подозреваю , что неизвестно, будет ли (в противном случае будет одним возможный ответ на этот вопрос). Если не известно, существует ли разделение...
Как все знают, SAT завершен для сравнению с многозначным сокращением за полиномиальное время. Это все еще полные сокращения wrt много-один.NPNP\mathsf{NP}AC0AC0\mathsf{AC^0} Мои вопросы: какова минимальная необходимая глубина для сокращений? Более формально, Что наименьшее такое, что SAT - это...
Я читаю приложение о АССЕ нижних границах для NEXP в Arora и Барак вычислительной сложности книги. http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf Одна из ключевых лемм - это преобразование из цепей в полилинейные полиномы над целыми числами с полилогарифмической степенью и...
Я посмотрел в Интернете, но не смог найти «большой список» вариантов проблемы SAT. Помимо (общего) СИДЕЛ, к-СБ, MAX-КСАТ, Half-СБ, XOR-СБ, НАЗ-СБ какие еще варианты есть? (также будет очень полезно, если есть классы сложности (где это...
Лемма: Предполагая, что эта эквивалентность у нас есть (\x -> ⊥) = ⊥ :: A -> B. Доказательство: ⊥ = (\x -> ⊥ x)по eta-эквивалентности и (\x -> ⊥ x) = (\x -> ⊥)по сокращению под лямбду. В отчете Haskell 2010, раздел 6.2, seqфункция определяется двумя уравнениями: seq :: a -> b...
Известно , что если проблема оценки цепи в N C 1 ? Как насчет A L о г т я м е (Uniform N C 1 )?NC1NC1\mathsf{NC^1}NC1NC1\mathsf{NC^1}ALogTimeALogTime\mathsf{ALogTime}NC1NC1\mathsf{NC^1} Мы знаем, что схемы глубины могут быть оценены схемами глубины k + c, где c - универсальная постоянная. Это...