Я думаю, что я не понимаю этого, но ηη\eta -конверсия выглядит для меня как ββ\beta конверсия, которая ничего не делает, особый случай ββ\beta конверсии, где результатом является просто термин в лямбда-абстракции, потому что нечего делать, вид бессмысленного ββ\beta преобразования. Так что,...
Существует множество алгоритмов, которые могут анализировать грамматику без контекста за . Используя матричное умножение, можно даже пойти асимптотически быстрее, чем это.O(n3)O(n3)O(n^3) Тем не менее, все алгоритмы для разбора произвольных CFG, которые я знаю, имеют использование пространства в...
Операция с большинством голосов встречается довольно часто в отказоустойчивом (и, без сомнения, в других местах), где функция выводит бит, равный тому, какое значение всегда появляется в значении входных битов. Для простоты предположим, что всякий раз, когда вход содержит одинаковое количество...
XORification - это метод усложнения булевой функции или формулы путем замены каждой переменной на XOR k ≥ 2 различных переменных x 1 ⊕ … ⊕ x k . xxxk≥2k≥2k\geq 2x1⊕…⊕xkx1⊕…⊕xkx_1 \oplus \ldots \oplus x_k Мне известно об использовании этого метода для усложнения доказательства, главным образом для...
Является ли автоматическое доказательство теорем и поиск доказательств более простым в линейных и других пропозициональных субструктурных логиках, в которых отсутствует сжатие? Где я могу прочитать больше об автоматическом доказательстве теорем в этих логиках и роли сокращения в поиске...
Существуют ли алгоритмы решения SAT, не основанные на DPLL? Или все алгоритмы, используемые решателями SAT, основаны на
Хорошо известно, что квантовые компьютеры являются строго более мощными, чем их классические аналоги, с точки зрения сложности запросов . Существуют ли другие модели (естественные или искусственные), которые строго находятся между квантовой и классической с точки зрения сложности запросов?...
Я вижу много исследований в области гиперкомпьютеров в 1990-х, но в последние годы, кажется, мало работы по этой теме. Правда ли, что исследования в этой области прекратились? Если так, что может быть причинами этого? Была ли эта область убедительно показана...
Что известно о точной сложности самой короткой проблемы суперструн? Может ли это быть решено быстрее, чем O∗(2n)O∗(2n)O^*(2^n) ? Существуют ли известные алгоритмы, которые решают кратчайшую суперструну без сокращения до TSP? UPD: подавляет полиномиальные факторы.O∗(⋅)O∗(⋅)O^*(\cdot) Самая короткая...
Я думаю, что было бы неплохо составить список теорем, утверждающих, что P не равен NP, если и только если такие и такие выходы существуют, некоторый класс сложности содержится в другом классе сложности и так далее, и так далее....
Пусть F1F1F_1 - выполнимая формула CNF с nnn переменными и mmm предложениями. Пусть SF1SF1S_{F_1} - пространство решений F1F1F_1 . Рассмотрим проблему определения для данной F1F1F_1 другой формулы CNF F2F2F_2с тем же набором переменных, что и для F1F1F_1 , с SF2=SF1SF2=SF1S_{F_2} = S_{F_1} (то же...
ООOC ø N P O ⊆ P S P C E O Oc o N PОP я PОсоNпО⊈япО{\sf coNP}^O \not\subseteq {\sf IP}^Oc o N PО⊆ Р С Р С ЕОсоNпО⊆пSпAСЕО{\sf coNP}^O \subseteq {\sf PSPACE}^OООO Тем не менее, я видел только несколько человек, которые дают «прямое» объяснение того, почему результат не релятивизируется, и обычный...
Я работаю над набором задач для класса и подумал над вопросом, касающимся того, над чем я работал. Существует ли минимальное количество состояний, которое должен иметь конечный автомат, чтобы принимать двоичные строки, представляющие числа, кратные целому числу n? В более раннем наборе задач я смог...
Я искал далеко и широко для таких приложений и в основном оказался коротким. Я могу найти множество применений топологии и подобных структур на счетных (или неисчисляемых) наборах, но редко я нахожу неисчислимые наборы в качестве объекта изучения компьютерными учеными, что приводит к необходимости...
Каковы известные эффективные алгоритмы вычисления определителя целочисленной матрицы с коэффициентами в , кольца вычетов по модулю m . Число m может быть не простым, а составным (поэтому вычисления выполняются в кольце, а не в поле).ZмZм\mathbb{Z}_mммmммm Насколько я знаю (читайте ниже),...
Была ли проделана какая-либо работа над тем, как сложность случайных экземпляров # 2-SAT зависит от плотности предложения? То есть: как изменяется сложность подсчета удовлетворяющих решений для случайно сгенерированного экземпляра 2-SAT , когда меняется плотность предложений? В частности, известны...
Предположим, что TTT - дерево постоянной степени, структура которого мы не знаем. Проблема состоит в том, чтобы вывести дерево , задавая запросы в форме: «Находится ли узел на пути от узла к узлу ?». Предположим, что на каждый запрос оракул может ответить в постоянное время. Мы знаем значение ,...
Как вы знаете, существует много аномалий для одиночных ленточных машин Тьюринга, когда время : симуляция ТМ с несколькими лентами, симуляция большого алфавита ленты с просто { 0 , 1 , b } , возможность построения времени, неплотность теоремы иерархии времени,...
Сложность зоопарк не имеет много о SCSC\mathsf{SC} . Я ищу хорошую † проблему, которая находится на более высоких уровнях иерархии, то есть проблему в D T i m e S p a c e ( n O ( 1 ) , lg O ( 1 ) n ), но о которой неизвестно в D Т я м ē S р с е ( п O ( 1...
В глубине души я физик, и поэтому я считаю, что односторонние квантовые вычисления великолепны. В частности, Quantum Computing (MBQC), основанная на измерениях графических состояний, была действительно хорошей разработкой в исследованиях Quantum Computing, созданной Raussendorf & Briegel ....