Недавно я наткнулся на статью Кудрона и Юена о расширении случайности с использованием квантовых устройств. Основным результатом работы является то, что можно генерировать «бесконечную» случайность из постоянного числа источников (то есть количество генерируемых случайных битов зависит только от...
В противоположной формуле CNF с двойным чтением каждая переменная появляется дважды, один раз положительный и один раз отрицательный. Меня интересует проблема , которая заключается в вычислении четности числа удовлетворяющих назначений противоположной формуле CNF с .⊕...
Пусть , быть ориентированный ациклический граф , и пусть - функция маркировки отображения каждой вершины с меткой в некотором конечном алфавите . Запись, А топологическая сортировка из является взаимно однозначное от к (т.е., упорядочение в последовательности) таким образом, что всякий раз , когда...
Пусть GGG - общий оракул в смысле категории Коэна / Бэра. Пусть RRR случайный оракул. Существуют ли классы сложности A и B с AG=BGandAR≠BRAG=BGandAR≠BR\mathrm{A}^G=\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R\ne \mathrm{B}^R или наоборот,...
В целом решение о том, имеет ли диофантово уравнение какое-либо целочисленное решение, эквивалентно проблеме остановки. Я считаю, что решение о том, имеет ли какое-либо решение квадратное диофантово уравнение, является NP-полным. Существует ли дополнительное ограничение на используемые уравнения,...
Общий вопрос Обобщает ли теорема о пространственной иерархии неравномерное вычисление? Вот несколько более конкретных вопросов: Является ли ?L / ролу⊊ PSпA CЕ/ РолуL/poly⊊PSPACE/polyL/poly \subsetneq PSPACE/poly Для всех космических построимых функций , является D S Р С Е ( О ( е ( п ) ) ) / р о л...
Меня интересует классическая проблема РЕГУЛЯРНОГО ВКЛЮЧЕНИЯ ЯЗЫКА. Для регулярного выражения обозначим через L ( E ) связанный с ним регулярный язык. (Регулярные выражения на фиксированном алфавите Σ с объединением операций, звездой Клини и конкатенацией.)ЕЕEL ( E)L(Е)L(E)ΣΣ\Sigma Входные данные:...
Из теоремы о пространственной иерархии известно, что если конструируемо в пространстве, то DSPACE ( ) не равно DSPACE ( .еff2 f ( n ) f ( n ) )2 ф( н )2f(n)2f(n)е( н ) )f(n))f(n)) Здесь под DSPACE ( я подразумеваю класс всех задач, которые могут быть решены в пространстве машиной Тьюринга с...
Какие есть доказательства того, что ?c o R P≠ NпcoRP≠NPcoRP \neq NP c o R PcoRPcoRP - это класс языков, для которых существует вероятностная машина Тьюринга, которая работает за полиномиальное время и всегда отвечает Да на входе, принадлежащем языку, и отвечает Нет с вероятностью, по крайней мере,...
Возможно ли (вы можете дать пример косую черту) уменьшить вычислительную сложность задачи, используя параллельный алгоритм, который не требует количества процессоров относительно размера...
Под BPP / linear я подразумеваю машины BPP с линейным советом, который выполняет обещание, когда дается «правильный» совет, и дерандомизация должна дать нам, скажем, P / линейный или (SUBEXP / линейный) алгоритм. Если мы используем неоднородные предположения, я думаю, классические результаты должны...
Покажите функцию которая конструируется в пространстве, но не является временной.е( н )е(N)f(n) Связана ли эта проблема с возможным разделением между классами сложности DTIME (f (n)) и SPACE (f...
Звезда система представляет собой семейство п подмножеств п-элементов , установленных S . Звезда система графическая если есть граф G ( V , E ) таким образом, что Р является семейством окрестностей вершин в G . Это N P -полных , чтобы определить , является ли данная графическая система...
Примеры ограниченных полных вариантов неразрешимых множеств:NпNPNP Ограниченная задача остановки = { | NTM-машина останавливает и принимает течение шагов}М х т( М, х , 1T)(M,x,1t)(M, x, 1^t)MMMИксxxTtt Ограниченная плитка = { | есть плитка квадрата области плитками из }т 2 т( Т, 1T)(T,1t)(T,...
Меня интересуют "сложные" отдельные примеры NP-полных задач. Райан Уильямс обсудил проблему SAT0 в блоге Ричарда Липтона . SAT0 спрашивает, имеет ли экземпляр SAT конкретное решение, состоящее из всех 0. Это заставило меня задуматься о создании экземпляров SAT, которые, вероятно, будут «сложными»....
Есть ли у нас классы сложности, скажем, относительно средней сложности? Например, существует ли (именованный) класс сложности для задач, решение которых занимает ожидаемое полиномиальное время? Другой вопрос рассматривает сложность наилучшего случая , приведенную ниже. Есть ли класс (естественных)...
Предположим,п≠ NпP≠NPP \neq NP Давайте использовать следующие обозначения для тетратации (то есть. ).яaia{}^iaяа = аa⋅⋅⋅aя разia=aa⋅⋅⋅a⏟i times{}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}} | Х | это размер экземпляра х. Пусть L язык,L |е( i ) ≤ | х | < г( я ): =...
Неуязвимые генераторы определяются следующим образом: Пусть RRR - отношение NP, а MMM - машина, которая принимает L(R)L(R)L(R) . Неформально программа является неуязвимым генератором, если на входе 1n1n1^n она создает пары свидетельства экземпляра (x,w)∈R(x,w)∈R(x, w) \in R , где |x|=n|x|=n|x| = n...
Известен ли какой-либо класс сложности, содержащий онлайн-аналоги задач оптимизации? Если нет, то как можно определить такой класс? Мы знаем, что у многих проблем есть онлайн-версия: например, онлайн-версия проблемы с упаковкой бункера. Проблемы онлайн сложнее, если судить по их...
Интересно знать погоду есть редкий язык (даже построен с задержкой diagolanization) в НПИ в предположении , что .P≠NPP≠NPP \neq