Логический элемент И & ИЛИ - это логический элемент, который получает два входа и возвращает их И и ИЛИ. Могут ли схемы, выполненные только из логического элемента И & ИЛИ без разветвления, выполнять произвольные вычисления? Точнее, сводится ли пространство журналов вычислений за...
Есть ли вероятная гипотеза сложности / криптозащиты, которая исключает возможность того, что схемы полиномиального размера имеют субэкспоненциальный размер (т. Е. с ) ограниченной глубиной ( )...
Существует ли естественная проблема в P, для которой наилучшая известная временная граница имеет вид , где α - иррациональная
Классический результат состоит в том, что каждая схема 2 вентилятора И-ИЛИ-НЕ, которая вычисляет PARITY из входных переменных, имеет размер не менее и это является резким. (Мы определяем размер как число логических элементов И и ИЛИ.) Доказательством является устранение гейта, и, похоже, оно...
(Фон Нейман дал алгоритм, который имитирует честную монету при доступе к одинаковым смещенным монетам. Алгоритм потенциально требует бесконечного числа монет (хотя в ожидании достаточно конечного числа). Этот вопрос касается случая, когда допустимое количество бросков монет ограниченная.)...
преамбула Интерактивные системы доказательства и протоколы Артура-Мерлина были введены Голдвассером, Микали, Ракоффом и Бабаем еще в 1985 году. Сначала считалось, что первый более мощный, чем второй, но Голдвассер и Сипсер показали, что они обладают одинаковой силой ( в отношении признания языка)....
Мне интересно в широком смысле то, что известно о распараллеливании алгоритмов в P. Я нашел следующую статью в Википедии на эту тему: http://en.wikipedia.org/wiki/NC_%28complexity%29 Статья содержит следующее предложение: Неизвестно, является ли NC = P, но большинство исследователей подозревают,...
Рассмотрим следующие рассуждения: Пусть обозначим сложность Колмогорова из строки . Теорема Чайтена о неполноте гласит, чтохК( х )K(x)K(x)Иксxx для любой последовательной и достаточно сильной формальной системы , существует постоянную (зависящую только от формальной системы и ее языка), что для...
f(n)е(N)f(n) c > 0limn→∞nc/f(n)=0ИтN→∞Nс/е(N)знак равно0\lim_{n\rightarrow\infty} n^c/f(n)=0c>0с>0c>0 Ясно, что для любого языка справедливо, что для каждого суперполиномиального ограничения по времени . Интересно, верно ли и обратное утверждение этого утверждения? То есть, если мы знаем...
Используя алгоритм просмотра с переносом, мы можем вычислить сложение, используя полиномиальный размер семейства цепей 5 (или 4?) . Можно ли уменьшить глубину? Можем ли мы вычислить сложение двух двоичных чисел, используя семейство схем полиномиального размера с глубиной, меньшей глубины,...
Какова связь между алгоритмами ДНК и классами сложности, определенными с помощью машин Тьюринга? Как соотносятся меры сложности, такие как время и пространство, в ДНК-алгоритмах? Могут ли они быть использованы для решения проблем NP-complete, таких как TSP, которые машины фон Неймана не могут...
Я знаю, что сложность большинства разновидностей типизированных лямбда-исчислений без примитива Y-комбинатора ограничена, т. Е. Могут быть выражены только функции ограниченной сложности, причем граница увеличивается с ростом выразительности системы типов. Напомню, что, например, исчисление...
Лучшая известная верхняя граница для временной сложности умножения - это оценка Мартина Фюрера , которая является более чем линейной сложностью сложения по времени. Есть ли у нас доказательство того, что сложение по сути проще, чем умножение?журнал nп 2O ( журнал*н )NжурналN2О(журнал*N)n\log...
Хорошо известно, что следующая проблема является PSPACE-полной: Учитывая регулярное выражение , ?L ( β ) = Σ ∗ββ\betaL ( β) = Σ*L(β)=Σ∗L(\beta) = \Sigma^* Как насчет определения эквивалентности другим (фиксированным) регулярным выражениям ?αα\alpha Учитывая регулярное выражение , ?L ( β ) = L ( α...
Воодушевленный ответом Шора, связанным с различными представлениями о NP-полноте, я ищу проблему, которая является NP-полной при сокращениях P, но неизвестно, что она является NP-полной при сокращениях Logspace (предпочтительно в течение длительного времени). Кроме того, труднее ли найти сокращения...
Многие важные результаты в теории вычислительной сложности и, в частности, в теории «структурной» сложности, обладают интересным свойством, которое можно понять как фундаментально следующее (как я вижу это ...) из алгоритмических результатов, дающих эффективный алгоритм или протокол связи для...
Шор заявил в своем комментарии к ответу анонимного лося на этот вопрос. Можете ли вы определить сумму двух перестановок за полиномиальное время? То , что он является полным, чтобы определить разницу двух перестановок. К сожалению, я не вижу прямого сокращения от проблемы суммы перестановок, и было...
SSSI(n)={w∈S:|w|=n}I(n)={w∈S:|w|=n}I(n) = \{w \in S : |w| = n\}nnnT(w)T(w)T(w)AAAwwwAAAfn=maxw∈I(n)T(w).fn=maxw∈I(n)T(w). f_n = \max_{w \in I(n)} T(w). Теперь определим множества всех входов со сложностью Колмогорова и определим последовательность Здесь - средняя последовательность времени...
Недавно я прошел через мучительный забавный опыт неформального объяснения концепции вычислительной сложности молодому талантливому программисту-самоучке, который никогда раньше не проходил формальный курс по алгоритмам или сложности. Неудивительно, что многие понятия поначалу казались странными, но...
Следующая проблема недавно появилась в моем исследовании. Будучи не специалистом по алгоритмическим вопросам, я активно гуглил в поисках подходящих проблем, с которых можно было бы справиться. Я не понимаю, как будет работать 3SAT, и хотя ZOE схожи по духу, сокращение не очевидно. Другой...