Мотивация для этого вопроса - факт, что большинство n-битных строк несжимаемо. Интуитивно, мы можем предложить по аналогии, что большинство доказательств тавтологии несжимаемы до полиномиального размера. По сути, моя интуиция заключается в том, что некоторые доказательства по своей природе случайны...
Это продолжение моего предыдущего вопроса о нижних границах связи для частичных булевых функций . Может ли кто-нибудь предложить какую-либо ссылку на нижние границы для недетерминированного многопартийного общения? Я просматривал статьи в этой области, но все, кажется, демонстрируют разделение...
Дана Англюин ( 1987 ; pdf ) определяет модель обучения с помощью запросов на членство и теоретических запросов (контрпримеры к предложенной функции). Она показывает, что регулярный язык, представленный минимальным DFA из состояний, может быть изучен за полиномиальное время (где предложенные функции...
Это продолжение моего предыдущего вопроса: Лучшая известная нижняя оценка сложности времени для естественной задачи в NP Я нахожу удивительным, что мы не смогли доказать какую-либо квадратичную детерминированную нижнюю границу для любой интересной проблемы NP, которая интересует людей и пытается...
Короче говоря, теоремы иерархии времени говорят о том, что машина Тьюринга может решить больше проблем, если у нее будет больше времени для вычислений. Подробно для детерминированных TM и функций, построенных по времени, с это и для недетерминированных функций TM и функций времени, f, g с f (n + 1)...
В SODA 1995 года Джефф Эриксон показал нижние оценки линейной выполнимости (проверяя, удовлетворяет ли некоторое подмножество действительных чисел линейному уравнению на переменных). Метод доказательства использует бесконечно малые и принцип переноса Тарского .н рrrrnnnrrr Может ли кто-нибудь...
Позволять ЧАСA LTNHALTnHALT_n обозначить строку длины 2N2n2^n соответствует таблице истинности проблемы остановки для входов длины Nnn, Если последовательность колмогоровских сложностей К( HA LTN)K(HALTn)K(HALT_n) мы O ( 1 )O(1)O(1), тогда одна из строк рекомендаций будет использоваться бесконечно...
Я хотел бы знать текущее состояние фазового перехода для случайных k-sat, учитывая n переменных и m предложений, что является наиболее известным c = m / n для верхней и нижней...
Следующий вопрос связан с оптимальностью алгоритма динамического программирования Беллмана-Форда - кратчайшего пути (см. Этот пост для связи). Кроме того, положительный ответ будет означать, что минимальный размер монотонной недетерминированной программы ветвления для задачи STCONN равен . t Θ ( n...
В сложности дерева решений для булевой функции очень хорошо известный метод нижней границы состоит в том, чтобы найти (приблизительный) многочлен, который представляет функцию. Патури дал характеристику для симметричных булевых (частичных и полных) функций в терминах величины, обозначаемой...
Я считаю , что ответы на этот вопрос зависит классы дают такое , что для всех полиномов , существует проблема в классе , который не имеет схемы размера . Однако я спрашиваю о размере схемы .pppp(n)p(n)p(n)ω(n)ω(n)\omega \hspace{.02 in}(n)...
Изменить: теперь есть дополнительный вопрос, связанный с этим сообщением. Определения Позволять ccc а также kkkбыть целыми числами. Мы используем обозначения[i]={1,2,...,i}[i]={1,2,...,i}[i] = \{1,2,...,i\}, c×cc×cc \times c матрица M=(mi,j)M=(mi,j)M = (m_{i,j}) Говорят, что ccc-До-kkkраскраска,...
Хорошо известно, что сложность квантового запроса с ограниченной функцией функции равна . Теперь вопрос в том, что если мы хотим, чтобы наш квантовый алгоритм работал успешно для каждого входа с вероятностью а не обычным . Теперь с точки зрения какие будут соответствующие верхние и нижние...
Я смущен. Я хочу доказать, что это проблема сортировкиnNn по nnn матрица, т.е. строки и столбцы в порядке возрастания Ω(n2logn)Ω(n2logn)\Omega(n^2\log n), Я исхожу из предположения, что это можно сделать быстрее, чемn2lognn2lognn^2\log n и попытаться нарушить log(m!)log(m!)\log(m!) нижняя...
Я столкнулся со следующим вопросом, который является легким упражнением (спойлер ниже). Нам дают nnnэкземпляры проблемы остановки (т. е. ТМ ), и нам нужно решить, какие именно из них останавливаются на . То есть нам нужно вывести . Нам дан оракул для решения проблемы остановки, но мы должны...
Два стека могут быть эффективно реализованы с использованием одного массива фиксированного размера: стек № 1 начинается с левого конца и увеличивается вправо, а стек № 2 начинается с правого конца и увеличивается влево. Возможно ли то же самое для трех стеков? Более конкретно, возможно ли...