в 1979 году Хопкрофт / Ульман написал, что L ⊆ P ⊆ NP ⊆ PSpace известно, но L ⊊ PSpace является единственным известным (и тривиальным) сдерживанием, известным, хотя все предполагаются как надлежащие сдерживания, и «где вещи все еще стоят» ~ 4 десятилетия спустя , с тех пор существует ли какая-либо...
«Если , существует ли x , y ∈ N , a x 2 + b y = c » является N P -полным.a,b,c∈Na,b,c∈Na,b,c\in\Bbb Nx,y∈Nx,y∈Nx,y\in\Bbb Nax2+by=cax2+by=cax^2+by=cNPNP\mathsf{NP} К какому классу сложности относится «При условии , существуют ли x , y ∈ N , a x 2 + b y 2 = c »?a,b,c∈Na,b,c∈Na,b,c\in\Bbb...
Пусть о Л -терминов быть определены следующим образом :sizesizesizeλλ\lambda ,size(x)=1size(x)=1size(x) = 1 size(λx.t)=size(t)+1size(λx.t)=size(t)+1size(λx.t) = size(t) + 1 , size(ts)=size(t)+size(s)+1size(ts)=size(t)+size(s)+1size(t s) = size(t) + size(s) + 1 . Пусть сложность -term определяется...
Сокращение Карпа - это вычисляемое многочленное сокращение многочлена за полиномиальное время между двумя вычислительными задачами. Многие сокращения Карпа на самом деле являются функциями «один-один». В связи с этим возникает вопрос, является ли каждое редукция Карпа инъективной (однозначная...
Интересно, что произойдет, если в определении (полиномиальная иерархия, см., Например, здесь ) роль будет заменена на ?PHPHPHNPNPNPRPRPRP Кажется, мы все еще можем построить иерархию, так же, как строится , просто используя везде вместо и вместо . Давайте назовем это рандомизированной...
Учитывая композит 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...
Дана строка , А палиндром крышка представляет собой последовательность р 1 р 2 ⋯ р м слов р я такое , что р 1 р 2 ⋯ р м = ш , и так , что каждый р я палиндром ,w = σ1σ2… ΣNw=σ1σ2…σnw=\sigma_1\sigma_2\ldots\sigma_nп1п2⋯ рмp1p2⋯pmp_1p_2\cdots p_mпяpip_iп1п2⋯ рм= шp1p2⋯pm=wp_1p_2\cdots p_m = wпяpip_i...
Я интересуюсь математикой на TCS. Я хочу самостоятельно изучить алгоритмы и их сложность для решения групповых теоретических задач, таких как поиск порядка элементов, перечисление смежных классов, поиск генератора, проверка, генерирует ли данное подмножество группу. Какую книгу я должен...
Как я могу решить следующую рекуррентную связь? f(n)=f(n−1)+f(n−logn)f(n)=f(n−1)+f(n−logn) f(n) = f(n-1) + f(n - \log
СCC - параллельный оси прямоугольник. С1, … , CNC1,…,CnC_1,\dots,C_nC1∪⋯∪Cn⊊CC1∪⋯∪Cn⊊CC_1\cup\dots\cup C_n \subsetneq C Прямоугольник , сохраняющее разбиение на разбиение C = E_1 \ чашка \ ДоТы \ чашка E_N , таким образом, что N \ GEQ п , то e_i попарно-салона непересекающейся оси параллельных...
Greibach лихо определил язык , так называемую недетерминированную версию о , таких , что любая КЛЛ является обратной морфической изображение . Существует ли подобное утверждение с DCFL, возможно, с некоторыми ограничениями на допустимые морфизмы?D 2 HЧАСHHD2D2D_2ЧАСHH (См., Например, М. Аутеберт,...
Пусть обозначает минимальный размер (немонотонной) арифметической схемы, вычисляющей заданный полилинейный многочлен и обозначают минимальный размер (немонотонной) логической схемы, логическую версию для определяется как: ( + , × , - ) е ( х 1 , ... , х п ) = Σ е ∈ Е с й п Π я = 1 х е я яА (...
Я ищу обзорную статью о важных концепциях в области квантовых автоматов. Я нашел квантовую теорию автоматов - обзор Хирвенсало, но она звучит слишком кратко, чтобы понять тему. Существует ли достаточно всеобъемлющий опрос на тему квантовых автоматов? Кроме того, не могли бы вы указать мне...
Скажем, граф обладает свойством если его вершины можно упорядочить таким образом, чтобы граф индуцированный вершинами имел для всех . Другими словами, добавление следующей вершины в нашем порядке не влияет на метрику расстояния текущего графа.M v 1 , v 2 , … v n H i { v 1 , … , v i } d i s t H i (...
Предположим, мы хотим умножить матриц. Алгоритм медленного умножения матриц выполняется за время O ( n 3 ) и использует O ( n 2 ) памяти. Самое быстрое умножение матриц выполняется за время n ω + o ( 1 ) , где ω - постоянная линейной алгебры, но что известно о ее сложности памяти?n×nn×nn \times...
В этой лекционной заметке Олы Свенссон: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf говорится, что мы не знаем, находится ли евклидова TSP в NP: Причина в том, что мы не знаем, как эффективно рассчитать квадратные корни. С другой стороны, есть документ Пападимитриу:...
Я рассматриваю язык всех выполнимых логических формул высказываний, SAT (чтобы гарантировать, что у этого есть конечный алфавит, мы бы закодировали пропозициональные буквы некоторым подходящим способом [править: ответы указали, что ответ на вопрос, возможно, не является устойчивым при различные...
Легко наблюдение состоит в том, что если проблема разрешима недетерминированной программы полиномиальное время , используя O ( журнал N ) недетерминированных битов (то есть, все свидетели логарифмические в длину), то ∈ P .AAAO(logn)O(logn)O(\log n)A∈PA∈PA \in \mathsf{P} Если тогда кто-то задает...
Теорема иерархии времени утверждает, что машины Тьюринга могут решить больше проблем, если у них есть (достаточно) больше времени. Имеет ли это какое-то значение, если пространство ограничено асимптотически? Как DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n), O(s(n))) относится к...
Хорошо известно, что проблема остановки является неисчислимой. Тем не менее, можно экспоненциально «сжать» информацию о проблеме остановки, так что ее распаковка является вычислимой. Точнее, можно вычислить из описания машин Тьюринга и n- битного состояния рекомендации ответ на проблему остановки...