Пусть - перестановка. Обратите внимание, что хотя действует на бесконечной области, его описание может быть конечным. Под описанием я имею в виду программу, которая описывает функциональность . (Как и в колмогоровской сложности.) См. Пояснения ниже. π ππ:{0,1}∗→{0,1}∗π:{0,1}∗→{0,1}∗\pi \colon...
Резолюция - это схема, доказывающая неудовлетворенность CNF. Доказательством в резолюции является логический вывод пустого предложения для начальных предложений в CNF. В частности, любой начальный пункт может быть выведен, и из двух пунктов и B ∨ ¬ x также может быть выведен пункт A ∨ B....
Фон Сложность схемы определяется как набор семейств схем (т. Е. Последовательности схем, по одной для каждого входного размера) ограниченной глубины и полиномиального размера, построенных с использованием неограниченного разветвления И, ИЛИ и НЕ.A C0AC0AC^0 Функция четности с n- битным входом равна...
В этом вопросе было отмечено, что существуют версии описательной сложности теоремы Райса. Я нашел доказательство следующей теоремы: Учитывая класс сложности C , нетривиальные свойства языков в C не могут быть вычислены в C Ранее я опубликовал найденное мной доказательство, но поскольку оно было...
Учитывая булеву схему для переменных (которая использует только вентили NOT, AND и OR), каков наиболее эффективный способ извлечь логическую формулу, представленную схемой? Есть ли алгоритм Polytime для этой...
Я просматривал оригинальную статью Les Valiant, и мне было тяжело с предложением 4.3 на странице 10 статьи. Я не могу понять, почему это так, что если существует генератор с определенными значениями для с базисом { ( a 1 , b 1 ) … ( a r , b r ) } , то существует некоторый генератор с таким же v a l...
Я играл с очень интересным и все еще открытым вопросом « Азбука одноленточной машины Тьюринга » (Эмануэле Виола) и придумал следующий язык: L = { x ∈ { 0 , 1 }N ул | х | = n = 2м и c o u n t 1 ( x ) = k ∗ m ;n , m , k ≥ 1 }L={x∈{0,1}n s.t. |x|=n=2m and count1(x)=k∗m;n,m,k≥1}L = \{ x \in \{0,1\}^n...
Короче говоря, теоремы иерархии времени говорят о том, что машина Тьюринга может решить больше проблем, если у нее будет больше времени для вычислений. Подробно для детерминированных TM и функций, построенных по времени, с это и для недетерминированных функций TM и функций времени, f, g с f (n + 1)...
Span-программа - это линейно-алгебраический способ задания булевой функции, представленный здесь . Недавно эта модель использовалась, чтобы показать, что метод отрицательного противника обеспечивает точную характеристику (по крайней мере, до ) сложности квантовых...
Чтобы ответить «какие проблемы можно решить с помощью вычислений», мы разработали теорию вычислимости. Для задач, которые являются вычислимыми, есть ли теория, чтобы ответить на вопрос «программа, которую я получаю, самая простая»? Я не думаю, что вычислительная сложность ответит на вопрос. Я...
Мы знаем, что log ранга матрицы 0-1 является нижней границей детерминированной сложности связи, а log приблизительного ранга является нижней границей рандомизированной сложности связи. Наибольший разрыв между детерминированной коммуникационной сложностью и рандомизированной коммуникационной...
Хотя экспоненциальное разделение между сложностью квантового запроса с ограниченной ошибкой ( Q ( f)Q(f)Q(f) ) и сложностью детерминированного запроса ( Д ( ф)D(f)D(f) ) или сложностью рандомизированного запроса с ограниченной ошибкой ( R ( f)R(f)R(f) ) известно, они применяются только к...
Монотонная формула CNF с m членами на n переменных ( ) - это формула вида , где каждый является ИЛИ некоторого подмножества переменных и находятся в диапазоне от до . f ( x 1 , … , x n ) = ⋀ C i C i x 1 , … , x n i 1 мИкс1, … , ХNИкс1,...,ИксNx_1,\ldots,x_nе( х1, … , ХN) = ⋀ Cяе(Икс1,...,ИксN)знак...
Мой вопрос касается эквивалентности безопасности различных односторонних функций-кандидатов, которые могут быть построены на основе сложности факторинга. Предполагая проблему ФАКТОРИНГ: [Дано для случайных простых чисел , найти , ]P , Q < 2 n P QN=PQN=PQN = PQP,Q<2nP,Q<2nP, Q < 2^nPPPQQQ...
Контекст: мы рассматриваем только орграфы. Пусть CYCLE будет языком графов с циклом; это NL-полная проблема. Пусть HASEDGE будет языком графов с хотя бы одним ребром. Тогда не тривиально, CYCLE∪HASEDGECYCLE∪HASEDGE\text{CYCLE} \cup \text{HASEDGE} больше не NL-трудно, в то время как...
Матрица Мура похожа на матрицу Вандермонда, но имеет слегка измененное определение. http://en.wikipedia.org/wiki/Moore_matrix Какова сложность вычисления определителя заданной n × nn×nn \times n матрицы Мура полного ранга по модулю некоторого целого числа? Можно ли уменьшить определитель Мура с O (...
Для неориентированного графа и данного множество S вершин, что является асимптотически быстрым известным алгоритма для нахождения простого пути , содержащий все элементы S . Что, если мы требуем, чтобы путь был максимально...
Имеет ли означают E = N E
Мой вопрос заключается в том, почему нижние оценки для логических схем глубины 3 с логическими элементами "и" и "xor" для определителя не подразумевают такие же нижние оценки для арифметических схем над ?ZZ\mathbb{Z} Что не так со следующим аргументом: Пусть - определитель, вычисляющий...
Следующий вопрос связан с оптимальностью алгоритма динамического программирования Беллмана-Форда - кратчайшего пути (см. Этот пост для связи). Кроме того, положительный ответ будет означать, что минимальный размер монотонной недетерминированной программы ветвления для задачи STCONN равен . t Θ ( n...