Вопросы с тегом «cc.complexity-theory»

17
Минимальная совокупная установленная сумма

Рассмотрим эту проблему: учитывая список конечных множеств, найдите порядок который минимизирует .s1,s2,s3,…s1,s2,s3,…s_1, s_2, s_3, \ldots|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots Есть ли известные алгоритмы для этого? В чем его...

17
Насколько распространен фазовый переход в NP-полных задачах?

Хорошо известно, что во многих NP-полных задачах наблюдается фазовый переход. Я заинтересован в фазовом переходе в отношении локализации на языке, а не в сложности ввода относительно алгоритма. Чтобы сделать понятие однозначным, давайте формально определим его следующим образом. Язык LLL...

17
Что такое оракул минимальной сложности, который отделяет PSPACE от полиномиальной иерархии?

Фон Известно , что существует оракул такое , что .P S P A C E A ≠ P H AAAAPSPACEA≠PHAPSPACEA≠PHAPSPACE^A \neq PH^A Даже известно, что разделение справедливо относительно случайного оракула. Неофициально можно интерпретировать это как означающее, что существует много оракулов, для которых и...

17
Пример, демонстрирующий силу недетерминированных цепей

Недетерминированная логическая схема имеет, помимо обычных входов , набор «недетерминированных» входов . Недетерминированная схема принимает вход если существует такой, что выход схемы включен . Аналогично (класс языков, разрешимых схемами полиномиального размера), можно определить как класс...

17
Можно ли зашифровать CNF?

Можно ли преобразовать CNF в другой CNF такой, чтобыCC\mathcal CΨ(C)Ψ(C)\Psi(\mathcal C) Функция может быть вычислена за полиномиальное время из некоторого секретного случайного параметра .ΨΨ\Psirrr Ψ(C)Ψ(C)\Psi(\mathcal C) имеет решение тогда и только тогда, когда имеет решение.CC\mathcal C Любое...

17
Список (нерешенных) проблем сложности, возникающих из PL

Какие основные открытые проблемы вычислительной сложности возникают из-за языков программирования, особенно из анализа и компиляции программ? Я ищу проблемы по линии «временная сложность вывода типа Хиндли-Милнера» или «временная сложность 0CFA» (хотя обе проблемы...

16
Какие

Знаменитая картина мира Нила Иммермана выглядит следующим образом (нажмите, чтобы увеличить):                                         Его «действительно выполнимый» класс не включает другого класса; мой вопрос тогда: Что такое проблема AC 0, которая считается непрактичной и почему?...

16
Взаимосвязь между симметрией и вычислительной непроницаемостью?

-fixed точки без проблем автоморфизма запрашивает автоморфизм графа , который перемещается по крайней мере , к ( п ) узлы. Проблема в том, что N P- полна, если k ( n ) = n c для любого c > 0.kkkk(n)k(n)k(n)NPNPNPk(n)=nck(n)=nck(n)=n^cccc Однако, если то задача полиномиального времени Тьюринга...

16
LogDCFL-полные проблемы

LogCFL - это набор всех языков, пространство логирования которых сводится к языку без контекста. Аналогично, LogDCFL - это набор всех языков, пространство логирования которых сводится к детерминированному контекстно-свободному языку. Смотрите эту статью в Википедии, чтобы узнать о некоторых...

16
Более сильные понятия униформизации?

Единственный пробел, который я всегда осознавал, что я на самом деле не понимаю, - это неравномерная и равномерная вычислительная сложность, где сложность схемы представляет собой неоднородную версию, а машины Тьюринга - это вещи, которые являются однородными. Я предполагаю, что «равномерный» - это...

16
Можем ли мы решить, есть ли у перманента уникальный термин?

Предположим, нам дана матрица n по n, M, с целочисленными элементами. Можем ли мы решить в P, существует ли перестановка такая, что для всех перестановок мы имеем ?σσ\sigmaπ≠ σπ≠σ\pi\ne\sigmaΠ Мя σ( я )≠ П Мя π( я )ΠMяσ(я)≠ΠMяπ(я)\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)} Замечания. Конечно, можно...

16
UGC твердость предиката

Фон : В оригинальной статье UGC Субхаша Хота ( PDF ) он доказывает, что UG-сложность определения того, допускает ли заданный экземпляр CSP ограничения всех форм Не-все-равные (a, b, c) по троичному алфавиту 1 - ограничений или не существует никаких заданий, удовлетворяющих 8ϵϵ\epsilonиз...

16
Релятивизируется ли псевдослучайный генератор Нисана?

Нисан доказал в «Псевдослучайных генераторах для пространственно-ограниченных вычислений», что существует псевдослучайный генератор, который «обманывает» ограниченные в пространстве вычисления. Эта конструкция справедлива для каждого оракула (по крайней мере, для неадаптивных...

16
Сложность гекса со случайным порядком поворота.

Я думал о варианте гексагона , где вместо двух игроков поочередно делают ходы, каждый ход, выбранный случайным образом, делает ход. Насколько сложно определить шансы каждого игрока на победу? Эта проблема, очевидно, есть в PSPACE, но не может ли она быть NP-сложной, а тем более PSPACE-полной....

16
Значение P = NP? зависит от геометрии пространства-времени?

Этот вопрос о странице 125 книги «Клеточные автоматы в гиперболических пространствах: Том 2» Мориса Маргенстерна, Publisher Archives современники, 2008. http://books.google.com/books?id=eEgvfic3A4kC&pg=PA125 По мнению автора, вопрос P = NP некорректен, поскольку в гиперболическом сеттинге P =...

16
Есть ли у «односторонних функций» какие-либо приложения вне криптографии?

Функция f:{0,1}∗→{0,1}∗f:{0,1}∗→{0,1}∗f \colon \{0, 1\}^* \to \{0, 1\}^* является односторонней, если fff может быть вычислена с помощью алгоритма полиномиального времени, но для каждого рандомизированного алгоритма полиномиального времени AAA,...

16
Существуют ли такие x, что K (xx) <K (x), где K - колмогоровская полнота.

Обозначим через колмогоровскую сложность строки x . Существуют ли такие строки, что K ( x x ) < K ( x ) . (Здесь x x - это сцепление x с самим собой). Похожий , но другой вопрос был задан здесь , но контрпример дается в ответ на этот вопрос не работает для...

16
Тавтологии / противоречия в среднем случае за пределами случайной модели k-CNF

Хорошо известно, что случайные формулы -CNF над n переменными с предложениями c n являются неудовлетворительными (т.е. являются противоречиями) с большой вероятностью для достаточно большой постоянной c . Таким образом, случайные формулы k- CNF (для достаточно больших c ) представляют собой...

16
Чтение на

Что я должен прочитать, чтобы понять эту проблему? Мощность квантовых цепей малой глубины. Является ли ? Другими словами, может ли «квантовая» часть любого квантового алгоритма быть сжата до глубины полилога (n), если мы хотим выполнить классическую постобработку за полиномиальное время? (Известно,...

16
Эффективная конкатенация ДФА?

Существует теоретическое доказательство того, что наивная декартова конструкция продукта для пересечения DFAs - «лучшее, что мы можем сделать». А как насчет объединения двух DFA? Тривиальная конструкция включает в себя преобразование каждого DFA в NFA, добавление эпсилон-перехода и определение...