Наиболее распространенный способ возникновения оракулов в теории сложности заключается в следующем: фиксированный оракул предоставляется, скажем, машине Тьюринга с определенными ограниченными ресурсами, и изучается, как оракул увеличивает вычислительную мощность машины. Есть, однако, другой способ,...
Этим летом я услышал, как Эмо Велцл говорит на эту тему. Я знаю, что число триангуляций набора из точек на плоскости находится где-то между Ω ( 8,48 n ) и O ( 30 n ) . Извиняюсь, если я устарел; Обновления приветствуются.nnnΩ(8.48n)Ω(8.48n)\Omega(8.48^n)O(30n)O(30n)O(30^n) Я упомянул об этом в...
Я провел некоторый поиск по этому вопросу, но так или иначе не смог найти ответ. Гек ответил на это полностью. Благодарность
Я знаю, что (логарифмически много обращений к оракулу NP) эквивалентно P N P | | (полиномиальное количество параллельных запросов к NP oracle). Мне было интересно, "функциональные" версии этих классов также эквивалентны, то естьPNP[logN]PNP[logn]\mathsf{P}^{\mathsf{NP}[\log n]}пН П |...
Этот вопрос связан с одним из моих предыдущих вопросов, NP-трудными задачами на деревьях . Я ищу проблемы, которые являются P-полными на деревьях.
Были бы какие-нибудь серьезные последствия, если бы у SAT было самое большее субэкспоненциальное несогласованное доказательство или даже более сильно, у SAT были алгоритмы субэкспоненциального...
У меня есть серьезные проблемы с пониманием одного шага в статье Добкина и Киркпатрика о разделении многогранников. Я пытаюсь понять эту версию: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf Он утверждает, что после того, как мы знаем лучшее разделение и ,...
Этот вопрос вдохновлен комментарием Юкки Суомела к другому вопросу . Каковы примеры бесконечно больших, но локально конечных вычислительных задач (и алгоритмов)? Другими словами, каковы примеры вычислений, которые останавливаются за конечное время, когда каждая машина Тьюринга считывает и...
Рассмотрим проблему определения максимального количества рыцарей, которых можно разместить на шахматной доске, чтобы двое из них не атаковали друг друга. Ответ 32: найти идеальное соответствие не так уж и сложно (график, индуцированный ходами коня, является двудольным, и есть идеальное соответствие...
В заявлении Дж. М. Сискинда говорится: Сталин - оптимизирующий компилятор для Scheme, который выполняет статический анализ всей программы и использует результаты этого анализа для генерации чрезвычайно эффективного кода. Сталин использует большой набор методов статического анализа. Он выполняет...
Я внедряю некоторую системную часть, которая требует некоторой помощи. Поэтому я формулирую это как проблему графа, чтобы сделать его независимым от домена. Задача: Нам дан ориентированный ациклический граф . Без ограничения общности предположим, что G имеет ровно одну исходную вершину s и ровно...
Проблема пропускной способности графа определяется следующим образом. Учитывая график , A макет из является отображение один к одному из вершин на целые числа . Ширина полосы определяется какG=(V,E)G=(V,E)G=(V,E) fffGGGGGG{1,…,|V|}{1,…,|V|}\{1, \ldots, |V|\}fff...
Вопрос. В своей работе « Улучшенное моделирование цепей стабилизатора» Ааронсон и Готтесман утверждают, что имитация схемы CNOT является ⊕L-полной (при сокращении пространства журнала). Ясно, что оно содержится в ⊕L ; как держится результат твердости? Эквивалентно: есть ли сокращение...
В статье Бен-Дор / Галеви [1] приводится еще одно доказательство того, что перманент является -завершенным. В более поздней части статьи они показывают цепочку сокращений то время как постоянное значение сохраняется вдоль цепи. Так как число постоянных назначений формулы 3SAT может быть получено из...
Я интересуюсь ранней историей опубликованных результатов о пространственно-временных компромиссах общего назначения. В частности, я хочу знать, кто первым описал следующий тип алгоритма для вычисления вычисления, имеющего произвольный граф потока данных с степенью O (1), используя пространство,...
Интересно, как найти обхват разреженного неориентированного графа. Под разреженным я подразумеваю . Под оптимальным я подразумеваю минимальную временную сложность.|E|=O(|V|)|E|=O(|V|)|E|=O(|V|) Я думал о некоторой модификации алгоритма Тарьяна для неориентированных графов, но я не нашел хороших...
(уже просили на главном сайте , но просим также о лучшем освещении, извините) Так как я знал о сжатых структурах данных, мне отчаянно нужен хороший обзор последних событий в этой области. Я погуглил и прочитал много статей, которые я мог видеть в верхней части результатов Google по запросам сверху...
Насколько я могу судить, почти во всех реализациях QKD для исправления ошибок используется алгоритм CASCADE Brassard и Salvail . Действительно ли это самый известный метод исправления ошибок в общей последовательности случайных кубитов, или есть лучшее предложение, которое вместо этого следует...
Какова вычислительная сложность оптимизации различных функций над унитарной группой ?U( н )U(N)\mathcal{U}(n) Типичная задача, возникающая часто в квантовой теории информации, было бы максимизировать количество типа (или выше многочленов порядка в ) по всем унитарные матрицы . Является ли этот тип...
Было бы неплохо собрать список условий, которые подразумевают, что язык L без контекста является регулярным, то есть условия вида: «если данный CFG / PDA имеет свойство P, то его языки являются регулярными» Свойство P не должно характеризовать CFG, генерирующие регулярные языки. Кроме того, P не...