Несколько лет назад Джоэл Фридман сделал несколько работ, касающихся нижних границ цепей для когомологий Гротендика (см. Документы: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024. ). Принесло ли это направление мысли новое понимание булевой сложности, или это скорее...
Как любитель TCS, я читаю некоторые очень вводные материалы по квантовым вычислениям. Вот несколько элементарных кусочков информации, которые я узнал до сих пор: Известно, что квантовые компьютеры не решают NP-полных задач за полиномиальное время. «Квантовой магии будет недостаточно» (Беннетт и...
Определите LOGLOG как класс языков, которые можно вычислить в пространстве O (loglog n) с помощью детерминированной машины Тьюринга (с двусторонним доступом к входу). Аналогично определите NLOGLOG как класс языков, которые могут быть вычислены в пространстве O (log log n) недетерминированной...
Существует часто цитируемое философское обоснование полагать, что P! = NP даже без доказательств. Другие классы сложности имеют доказательства того, что они различны, потому что если нет, то будут «удивительные» последствия (например, крах полиномиальной иерархии). Мой вопрос: на чем основано...
Невозможно написать язык программирования, который позволяет всем машинам, которые останавливаются на всех входах, и никаким другим. Тем не менее, кажется, что легко определить такой язык программирования для любого стандартного класса сложности. В частности, мы можем определить язык, на котором мы...
В этом вопросе формула 3CNF означает формулу CNF, в которой каждое предложение включает ровно три различные переменные. Для константы 0 < s <1 Gap-3SAT s является следующей проблемой обещания: GAP-3sat сек экземпляра : а 3CNF формула φ. Да-обещание : φ выполнимо. Нет-обещание : Нет истину...
В статье «Гипотеза случайного оракула ложна» авторы (Чанг, Чор, Гольдрайх, Хартманис, Хостад, Ранджан и Рохатхи) обсуждают значение гипотезы о случайном оракуле . Они утверждают, что мы очень мало знаем о разделениях между классами сложности, и большинство результатов включают либо использование...
Этот вопрос касается проблем, для которых существует большой открытый разрыв сложности между известной нижней границей и верхней границей, но не из-за открытых проблем самих классов сложности. Чтобы быть более точным, скажем, у проблемы есть классы промежутков A,BA,BA,B (с , не определенным...
Вокруг множество проблем с NP-полнотой, и источники их собирают, например, см. Книгу Гэри и Джонсона. Мне было бы интересно увидеть список неполных NEXP задач. Есть ли один доступный? Поскольку я предполагаю, что нет, я открываю этот вопрос (это должна быть вики сообщества? Я не знаю об этом...
ST-связность - это проблема определения, существует ли направленный путь между двумя выделенными вершинами и в ориентированном графе . Может ли эта проблема быть решена в пространстве журналов, является давней открытой проблемой. Это называется проблемой противssstttG(V,E)G(V,E)G(V,E)NLNLNLLLL В...
В этом гостевом посте Джоша Грохова в блоге о сложности он рассказывает о недавнем семинаре, посвященном GCT, который прошел в Принстоне в июле. Несколько участников утверждали, что мы должны использовать GCT, чтобы атаковать более простые проблемы, чем против N PпP\mathsf{P}Н ПNP\mathsf{NP} ,...
Решение, если количественная логическая формула, такая как ∀ х1∃ х2∀ х3⋯ ∃ хNφ ( х1, х2, … , ХN) ,∀Икс1∃Икс2∀Икс3⋯∃ИксNφ(Икс1,Икс2,...,ИксN),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), всегда оценивается как истина - это классическая PSPACE-полная проблема....
Я был (и до сих пор) действительно заинтересован в ответе на этот вопрос, потому что это интересный вариант сложности игр, который не был решен, поэтому я предложил вознаграждение. Я подумал, что исходный вопрос, скорее всего, слишком сложный, поэтому я опубликовал три связанных вопроса, которые...
Позволять L={n:the nth binary digit of π is 1}L={n:the nth binary digit of π is 1}L = \{ n : \text{the }n^{th}\text{ binary digit of }\pi\text{ is }1 \} (где считается закодированным в двоичном виде). Тогда что мы можем сказать о вычислительной сложности ? Понятно, что . И если я не ошибаюсь,...
Я думал, что поделюсь этим вопросом, так как он может быть интересен для других пользователей здесь. Предположим, что функция из однородного класса (например, ) также входит в небольшой неоднородный класс (например, A C 0 / p o l y , т. Е. Неоднородный A C 0 ), означает ли это, что функция...
Предполагая, что P! = NP, я полагаю, что было показано, что есть проблемы, которых нет в P и не NP-Complete. Предполагается, что изоморфизм графов является такой проблемой. Есть ли доказательства наличия таких «слоев» в NP? т.е. иерархия из более чем трех классов, начинающихся с P и заканчивающихся...
Я хотел бы найти алгоритм полиномиального времени, который определяет, содержит ли диапазон данного набора матриц матрицу перестановок. Если кто-нибудь знает, относится ли эта проблема к другому классу сложности, это было бы так же полезно. РЕДАКТИРОВАТЬ: я пометил этот вопрос с помощью линейного...
Если мы посмотрим на теорему об иерархии DTIME, то получим журнал из-за накладных расходов при моделировании детерминированной машины Тьюринга на универсальной машине: DTIME(flogf)⊊DTIME(f)DTIME(flogf)⊊DTIME(f)DTIME(\frac{f}{\log f}) \subsetneq DTIME(f) У нас нет такого рода накладных расходов на...
Определим - S U B E X P как класс языков L , для которого существует язык L ′ ∈ ∩ ε > 0 T I M E ( 2 n ε ) и для бесконечного множества n , L и L ′ согласны на всех экземплярах длины n . (То есть это класс языков, которые могут быть «решены бесконечно часто, в субэкспоненциальном...
Цитируя Википедию , «[Игра Жизни Конвея] обладает мощью универсальной машины Тьюринга: то есть все, что может быть вычислено алгоритмически, может быть вычислено в Игре Жизни Конвея». Распространяются ли такие результаты на шумные версии игры жизни Конвея? Простейшая версия состоит в том, что после...