Меня интересует естественное обобщение знаменитой 15-головоломки , где вам нужно сдвигать блоки, пока вы не отсортируете все заданные числа (обычно есть разрыв в 1 блок). Теперь обобщение должно было бы увеличить размер головоломки с 15 до , где одно поле свободно. Я создал небольшую иллюстрацию...
Сложность Zoo указывает в записи на EXP, что если L = P, то PSPACE = EXP. Поскольку NPSPACE = PSPACE от Savitch, насколько я могу судить, нижележащий аргумент отступа расширяется, чтобы показать, что Мы также знаем, что L NL NC P через ограниченную по ресурсам чередующуюся...
Это наивный вопрос, из моего опыта; заранее извиняюсь. Гипотеза Гольдбаха и многие другие нерешенные вопросы математики могут быть записаны в виде кратких формул в исчислении предикатов. Например, статья Кука "Могут ли компьютеры регулярно находить математические доказательства?" формулирует эту...
Вычислительная сложность включает в себя изучение временной или пространственной сложности вычислительных задач. С точки зрения мобильных вычислений энергия является очень ценным вычислительным ресурсом. Итак, есть ли хорошо изученная адаптация машин Тьюринга, учитывающая энергию, потребляемую при...
В своей книге «Вычислительная сложность» Пападимитриу пишет: RP в некотором смысле новый и необычный вид сложности класса. Ни одна полиномиально ограниченная недетерминированная машина Тьюринга не может быть основой для определения языка в RP. Чтобы машина N могла определить язык в RP , она должна...
Пусть AAA будет фиксированным положительным целым числом размером nnn бит. Разрешается предварительно обрабатывать это целое число соответствующим образом. Учитывая другое положительное целое число BBB размером mmm битов, какова сложность умножения ABABAB ? Обратите внимание, что у нас уже есть...
Недавно Гил Калай и Дик Липтон написали хорошую статью на интересную гипотезу, предложенную Питером Сарнаком, экспертом по теории чисел и гипотезе Римана. Гипотеза. Пусть - функция Мёбиуса . Предположим, что является функцией с входом в виде двоичного представления , тогда f : N → { - 1 , 1 }µ ( k...
Каковы были самые удивительные результаты в сложности? Я думаю, что было бы полезно иметь список неожиданных / неожиданных результатов. Это включает в себя как результаты, которые были неожиданными и появились из ниоткуда, так и результаты, которые оказались не такими, как ожидалось. Редактировать...
Проблема минимальной пропускной способности состоит в том, чтобы найти порядок узлов графа на целочисленной линии, который минимизирует наибольшее расстояние между любыми двумя соседними узлами. -caterpillar дерево формируется из основного пути, выращивая реберно непересекающихся путей длины не...
Многие считают, что . Однако мы только знаем, что находится на втором уровне полиномиальной иерархии, то есть . Шаг к показу состоит в том, чтобы сначала перевести его на первый уровень полиномиальной иерархии, то есть .BPPPNPBPP=P⊆NP\mathsf{BPP} = \mathsf{P} \subseteq...
Факторинг не известен как NP-полный. Этот вопрос задавался о последствиях факторинга, являющегося NP-полным. Любопытно, что никто не спрашивал о последствиях факторинга в P (возможно, потому что такой вопрос тривиален). Итак, мои вопросы: Какими будут теоретические последствия факторинга в P? Как...
Мы часто слышим о классических исследованиях и публикациях в области вычислительной сложности (Тьюринг, Кук, Карп, Хартманис, Разборов и др.). Мне было интересно, есть ли недавно опубликованные статьи, которые считаются основополагающими и должны быть прочитаны. Под недавним я имею в виду последние...
Несколько лет назад Джоэл Фридман сделал несколько работ, касающихся нижних границ цепей для когомологий Гротендика (см. Документы: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024. ). Принесло ли это направление мысли новое понимание булевой сложности, или это скорее...
Центральная проблема теории сложности, возможно, против .Н ПпPPNпNPNP Однако, поскольку Природа является квантовой, представляется более естественным рассмотреть классы (т. Е. Задачи решения, решаемые квантовым компьютером за полиномиальное время с вероятностью ошибки не более 1/3 для всех случаев)...
С общей точки смысле зрения, легко поверить , что добавление индетерминизм к значительно расширяет свою власть, т.е. N P гораздо больше , чем P . В конце концов, недетерминизм допускает экспоненциальный параллелизм, который, несомненно, кажется очень мощным. PP\mathsf{P}NPNP\mathsf{NP}PP\mathsf{P}...
Мы знаем, что если у вас есть машина PSPACE, она достаточно мощна, чтобы предоставить интерактивное доказательство любого уровня полиномиальной иерархии. (И если я правильно помню, все, что вам нужно, это #P.) Но предположим, что вы хотите предоставить интерактивное подтверждение членства на языке...
В 1995 году Рассел Импальяццо предложил пять миров сложности: 1- Алгоритмика: со всеми удивительными последствиями.P=NPP=NPP=NP 2- Эвристика: -полные проблемы трудны в худшем случае ( P ≠ N P ), но эффективно решаемы в среднем случае.NPNPNPP≠NPP≠NPP \ne NP 3- Пессиланд: Существуют -полные проблемы...
Как любитель TCS, я читаю некоторые очень вводные материалы по квантовым вычислениям. Вот несколько элементарных кусочков информации, которые я узнал до сих пор: Известно, что квантовые компьютеры не решают NP-полных задач за полиномиальное время. «Квантовой магии будет недостаточно» (Беннетт и...
Я взял класс один раз по вычислимости и логики. Материал содержал корреляцию между классами сложности / вычислимости (R, RE, co-RE, P, NP, Logspace, ...) и логикой (исчисление предикатов, логика первого порядка, ...). Корреляция включала в себя несколько результатов в одной области, которые были...
Рассмотрим следующую проблему подсчета (или связанную с ней проблему решения): учитывая два натуральных числа, закодированных в двоичном виде, вычислим их наибольший общий делитель (gcd). В каком классе наименьшей сложности содержится эта проблема? Можете ли вы предоставить ссылку? В этом вопросе...