Я ищу обзорную статью о важных концепциях в области квантовых автоматов. Я нашел квантовую теорию автоматов - обзор Хирвенсало, но она звучит слишком кратко, чтобы понять тему. Существует ли достаточно всеобъемлющий опрос на тему квантовых автоматов? Кроме того, не могли бы вы указать мне...
Уникальная SAT является хорошо известной проблемой: учитывая формулу CNF , верно ли, что F имеет ровно одну модель?FFFFFF Меня интересует проблема «точно -SAT»: учитывая формулу CNF F и целое число m > 1 , правда ли, что F имеет ровно m моделей?мmmFFFm > 1m>1m>1FFFmmm Обе проблемы выглядят...
Кто первым показал, что язык находится в NP, если сертификат для языка можно проверить за полиномиальное время? У нас есть документ, который формально доказывает это? Когда сообщество TCS начало преуменьшать недетерминизм в пользу проверяемости? Для жизни я не могу найти хорошую ссылку на это...
Какова минимальная ширина дерева схемы над для вычисления MAJ?{∧,∨,¬}{∧,∨,¬}\{\wedge,\vee,\neg\} Здесь MAJ выводит 1, если хотя бы половина его входов равна .1:{0,1}n→{0,1}:{0,1}n→{0,1}:\{0,1\}^n \rightarrow \{0,1\}111 Я забочусь только о размере схемы (должен быть полиномиальным) и о том, что...
Я прочитал статью Фрейда «Алгебраически полные категории» в известной книге Como90, и у меня есть два вопроса о понятии алгебраической компактности, которое он определил в этой статье. (Если вы не знакомы с определением, вот оно: категория называется алгебраически компактной, если каждый...
Итак, мы все знаем нижнюю границу дерева сравнения на количество худших случаев сравнений, выполненных (детерминистическим) алгоритмом сортировки сравнений. Это не относится к рандомизированной сортировке сравнения (если мы измеряем ожидаемые сравнения для наихудшего случая). Например, для n = 4...
Я ищу библиографические ссылки для следующего алгоритма / проблемы: я назвал его "BiSelect" или "t-ary Select" или "Select in Union of Sorted Arrays", но я предполагаю, что он был представлен ранее под другим именем? проблема Рассмотрим следующую проблему: Для заданных непересекающихся...
Я совершенно уверен, что я не первый, кто принимает идею, которую я собираюсь представить. Однако было бы полезно, если бы я мог найти какую-либо литературу, связанную с этой идеей. Идея состоит в том, чтобы построить машину Тьюринга M со свойством, что если P = NP, то M будет решать 3-SAT за...
Есть исследователь, показывающий, что стирающий бит должен потреблять энергию, а сейчас проводится какое-либо исследование среднего потребления энергии алгоритмом с вычислительной сложностью ? Я предполагаю, что вычислительная сложность F ( n ) коррелирует со средним потреблением энергии, надеюсь,...
Я надеюсь, что кто-то знает ссылку на это, поэтому мне не нужно читать литературу ... Рассмотрим последовательность чисел . Думайте о последовательности как о n - 1 интервалах [ x 1 , x 2 ] , [ x 2 , x 3 ] , … , [ x n - 1 , x n ] . Ясно, что исходная последовательность является битовой, если любая...
MPA (многопробельный автомат) - это 2DFA (двусторонний детерминированный конечный автомат), который может использовать произвольное количество камешков (на самом деле самое большее камешков на заданном входе - вход записывается на ленту между двумя концами -маркер как ). Во время вычисления MPA...
Я читаю обзоры Тревизана и Ловетта о применении аддитивного комбинаторика в TCS. Большинство этих приложений подпадают под сложность вычислений , например, нижние границы. Интересно, нашла ли аддитивная комбинаторика применение в разработке алгоритмов ? Мотивация для моего вопроса заключается в...
Если вам дан набор частичных заказов, топологическая сортировка скажет вам, есть ли расширение коллекции до общего заказа (в данном случае расширение представляет собой общий заказ, соответствующий каждому из частичных заказов). Я встретил вариант: Зафиксируем множество . Вам даны...
Таким образом, быстрый поиск в сети привел меня к мысли, что «APXHardness подразумевает, что для проблемы не существует QPTAS, если [некоторый класс сложности] не включен в некоторый [другой класс сложности]», и это тоже хорошо известно! Кажется, все это знают, кроме меня. К сожалению, нет никаких...
Симплексный алгоритм часто трактуется либо в реальной арифметике, либо в дискретном мире с точными вычислениями. Однако, это, кажется, чаще всего реализуется с помощью арифметики с плавающей точкой. Это приводит к вопросу, следует ли рассматривать симплексный алгоритм как числовой алгоритм, в...
Учитывая композит N∈NN∈NN\in\Bbb N общего числа поля решета является наиболее известным алгоритмом факторизации для целого факторизации NNN . Это рандомизированный алгоритм, и мы получаем ожидаемую сложность O(e649√(logN)13(loglogN)23)O(e649(logN)13(loglogN)23)O\Big(e^{\sqrt{\frac{64}{9}}(\log...
В настоящее время я занимаюсь исследованиями Формального языка, в которых участвуют классы языков выше обычного, но ниже контекста. Я смотрю на такие вещи, как машины с множеством счетчиков с ограниченным обращением, счетчики с одним стеком, детерминированные КЛЛ и т. Д. Мне интересно, знает ли...
Знаем ли мы, что иерархия не разрушается ( T C 0 d ⊊ T C 0 d + 1 для всех d )?Т С0TC0\mathsf{TC^0}TC0d⊊TC0d+1TCd0⊊TCd+10\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}ddd В записи Zoo для TC0TC0\mathsf{TC^0} упоминается только расстояние между глубиной 2 и 3. Кроме того, есть стандартная ссылка на...
Я интересуюсь математикой на TCS. Я хочу самостоятельно изучить алгоритмы и их сложность для решения групповых теоретических задач, таких как поиск порядка элементов, перечисление смежных классов, поиск генератора, проверка, генерирует ли данное подмножество группу. Какую книгу я должен...
В графе независимое множество - это подмножество вершин, которое не содержит ребра в качестве индуцированного подграфа. Проблема нахождения наибольших независимых множеств в графе является фундаментальным и сложным в этом вопросе. Давайте рассмотрим более общий вопрос поиска (размера) наибольшего...