Дана матрица A с рациональными элементами. В чем сложность проверки А диагонализируемой?n × nN×Nn\times nAAAAAA Я подозреваю, что это может быть сделано в P, но я не знаю никаких ссылок. Однако, более интересный вопрос, есть ли лучший класс сложности для решения этой проблемы? Любое руководство /...
Неформально односторонние функции определены в отношении алгоритмов PTIME. Они вычислимы за полиномиальное время, но не обратимы в полиномиальное время среднего случая. Существование таких функций является важной открытой проблемой в теоретической информатике. Я заинтересован в односторонних...
Пусть - булева функция от n булевых переменных. Пусть g ( x ) = T ϵ ( f ) ( x ) будет ожидаемым значением f ( y ), когда y получается из x путем переключения каждой координаты с вероятностью ϵ / 2 .fffnnng(x)=Tϵ(f)(x)g(x)=Tϵ(f)(x)g(x)=T_\epsilon (f) (x)f(y)f(y)f(y)yyyxxxϵ/2ϵ/2\epsilon/2 Меня...
Насколько я понимаю, доказательство того, что P = NP или P ≠ NP, должно быть нерелятивизируемым (как в оракулах теории рекурсии). Практически все доказательства кажутся релятивизируемыми. Какие хорошие примеры , не являющиеся Релятивизуемых доказательств, из тех , что Р = NP / P ≠ NP доказательству...
Предположим, что P NP.≠≠\ne Теорема Ладнера гласит, что существуют промежуточные проблемы NP (проблемы в NP, которые не находятся ни в P, ни в NP-Complete). Я нашел несколько завуалированных ссылок в Интернете, которые предполагают (я думаю), что в NPI существует много «уровней» взаимно сводимых...
Могут ли все последующие одновременно выполняться? LsLsL_s содержится в для всех натуральных чисел . sLs+1Ls+1L_{s+1}sss L=⋃sLsL=⋃sLsL = \bigcup_s L_s - это язык всех конечных слов над .{0,1}{0,1}\{0,1\} Существует некоторый класс сложности и понятие соответствующего сокращения для такой , что для...
Недавний вопрос (см Последствия NP = PSPACE ) просил для "противных" последствий . Перечисляют ответы немало последствий обрушения, в том числе N P = C O N P и другие, обеспечивая множество причин полагать N P ≠ P S P A C E .NP=PSPACENP=PSPACENP=PSPACENP=coNPNP=coNPNP=coNPNP≠PSPACENP≠PSPACENP\neq...
Пусть - мажоритарная функция, т.е. f ( x ) = 1 тогда и только тогда, когда ∑ n i = 1 x i > n / 2 . Мне было интересно, есть ли простое доказательство следующего факта (под «простым» я подразумеваю не полагаться на вероятностный метод, как это сделал Valiant 84, или на сортировку сетей;...
Недавно я изучаю модель вычисления BSS (см., Например, Сложность и Реальные вычисления; Блум, Кукер, Шуб, Смейл.) Для вещественных чисел показано, что для заданной системы полиномов f 1 , ⋯ , f m ∈ R [ x 1 , ⋯ , x n ] существование нулей является N P R -полным. Однако мне интересно, если эти f...
Название немного вводит в заблуждение, но, надеюсь, вопрос не в следующем: Новый результат Грёнлунда и Петти, показывающий, что 3SUM имеет только сложность дерева решений, заставил меня задуматься:O(n3/2)O(n3/2)O(n^{3/2}) Есть ли простой пример проблемы со сложностью дерева решений но допускающей...
У меня сведение следующей проблемы с разделом к определенной проблеме планирования: Входные данные: список целых положительных чисел в неубывающем порядке.a1⩽⋯⩽ana1⩽⋯⩽ana_1\leqslant\cdots\leqslant a_n Вопрос: существует ли вектор такой,...
Фон: Сложность дерева решений или сложность запросов - это простая модель вычислений, определяемая следующим образом. Пусть - булева функция. Детерминированная сложность запроса , обозначаемая , представляет собой минимальное количество битов входных данных которые должны быть прочитаны (в худшем...
Учитывая алгоритм, работающий во время , мы можем преобразовать его в «тривиальное» однородное семейство цепей для той же самой задачи размера не более .≈ t ( n ) log t ( n )t(n)t(n)t(n)≈t(n)logt(n)≈t(n)logt(n)\approx t(n)\log t(n) С другой стороны, может случиться так, что у нас есть гораздо...
В проблеме расширяемости нам дают часть решения, и мы хотим решить, можем ли мы расширить ее до полного решения. Некоторые проблемы расширяемости эффективно разрешимы, в то время как другие проблемы расширяемости превращают легкую проблему в сложную. Например, теорема Кенига-Холла утверждает, что...
-hierarchy представляет собой иерархию классов полностью в параметризованном сложности, см Сложности Зоопарк определений. Альтернативное определение определяет используя взвешенную определимость для логики первого порядка, см. Учебник Флума и Гроэ...
Для группы перестановок на и двух векторов где - конечный алфавит, который здесь не совсем уместен, вопрос есть ли какой-нибудь такой, что где означает применение перестановки к ожидаемым образом.GGG[n]={1,⋯,n}[n]={1,⋯,n}[n]=\{1, \cdots, n\}u,v∈Γnu,v∈Γnu,v\in \Gamma^nΓΓ\Gammaπ∈Gπ∈G\pi\in...
Пока пишу небольшой пост о сложности видеоигр Nibbler и Snake ; Я обнаружил, что они оба могут быть смоделированы как задачи реконфигурации на плоских графах; и кажется маловероятным, что такие проблемы не были хорошо изучены в области планирования движения (представьте, например, цепочку связанных...
Что-нибудь известно о втором наименьшем - -резе в сети потока? Или, в общем, об этой проблеме:sssTTt Вход: сеть и число , все в двоичном виде. Выход: наименьшее - вырезать.NNNККkККksssTTt - й наименьший - разреза любые - вырезать, например , что существует ровно - порезы , чьи мощностиККksssTTt( S,...
P / poly - это класс задач решения, решаемых семейством булевых схем полиномиального размера. В качестве альтернативы его можно определить как машину Тьюринга за полиномиальное время, которая получает строку подсказки, которая имеет полиномиальный размер по n и основана исключительно на размере n....
Рассмотрим проблему, когда нам задают в качестве входных данных направленный ациклический граф G=(V,E)G=(V,E)G = (V, E) , функцию маркировки λλ\lambda из VVV в некоторый набор LLL с полным порядком...