После эквивалентных вопросов относительно NP-полноты (см. Вопрос о весе и заданный вопрос ) мне стало интересно, как эти атрибуты влияют на параметризованные проблемы. Какие задачи жесткого графа являются -твердыми на ориентированных графах, но фиксированными параметрами, которые можно отследить на...
Возможно, основным источником проблем с производительностью в Haskell является случай, когда программа по неосторожности создает поток неограниченной глубины - это вызывает как утечку памяти, так и потенциальное переполнение стека при оценке. Классический пример - определение sum = foldr (+) 0в...
В целом проблемы были классифицированы благодаря сложности вычислений. Но можно ли в дифференциальных уравнениях классифицировать дифференциальные уравнения в зависимости от их вычислительной структуры? Например, если неоднородное уравнение первого порядка сравнительно трудно решить, чем, скажем,...
Q . Какова сложность нахождения наибольшего объемаограниченная ячейка в Arrangment из гиперплоскостей в размерности г ?nnnddd Я чувствую, что должен это знать ... Но я не нахожу окончательной ссылки. Это ? Как насчет специализации d = 2 : ячейка с наибольшей площадью в расположении...
Существует открытая проблема в формальных языках, известная как проблема разделения; который кратко изложен как заданные две отдельные строки длины , насколько большой DFA требуется, чтобы «разделить» их, то есть принять одну строку, но отклонить другую.nnn Вот некоторые соответствующие документы 1...
Какова сложность следующей задачи ( P? NP-hard?):∈∈\in Входные данные: направленный ациклический граф , множество обратных ребер и два отдельных узла и .E ′ ⊂ V × V s tD=(V,E)D=(V,E)D=(V,E)E′⊂V×VE′⊂V×VE'\subset V\times Vsssttt Вопрос: Пусть обозначает граф, образованный добавлением к ребер из ....
В тестировании тождества полиномов мы ищем детерминированный алгоритм, чтобы вывести равенство двух полиномов . Дерандомизация известных эффективных рандомизированных алгоритмов и создание эффективного детерминированного алгоритма является важной открытой проблемой. Есть ли полная проблема для PIT,...
Учитывая две перестановки и h над n элементами (т.е. членами S n ), какова сложность вычисления порядка подгруппы, сгенерированной g , h ? Или просто решить, имеет ли подгруппа порядок n ! (т. е. все S н...
Это старая открытая проблема, справедлива ли теорема прямой суммы для детерминированной сложности коммуникации, то есть, является ли решение независимых случаев задачи в раз сложнее, чем решение одного случая. [FKNN95] показал следующие результаты:TTtTTt Отрицательный результат: есть частичная...
Пусть k > 0k>0k>0 фиксированная константа. Для целого числа Nnn мы хотим построить перестановку σ∈ SNσ∈Sn\sigma \in S_n такую, что: Конструкция использует постоянное время и пространство (т.е. предварительная обработка требует постоянного времени и пространства). Мы можем использовать...
Мне интересно, может ли существовать способ придать своего рода «нормальную форму» бинарным деревьям решений (BDT) в управляемом виде. Точнее: BDT - это дерево с внутренними узлами, помеченными логическими переменными, и листьями, помеченными 000 или 111 . BDT представляет логическую функцию...
Этот блог рассказывает о создании "извилистых маленьких лабиринтов" с помощью компьютера, перечисляя их. Перечисление может быть выполнено с использованием алгоритма Уилсона для получения UST , но я не помню формулы для того, сколько их там....
Пусть будет дано число . Рассмотрим следующий язык: L n = {Nnn .LN= {ш ш|w ∈ { 0 , 1 }N}Ln={ww|w∈{0,1}n}L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \} Словом, - это набор строк копирования длиной 2 n .LNLnL_n2 н2n2n Рассмотрим следующую функцию сложности состояний , в которой s ( n ) - это...
Пусть наследственный класс графов. (Наследственный = замкнуто относительно взятия индуцированных подграфов.) Пусть обозначит множество -vertex графов в . Допустим, что содержит почти все графы, если доля всех вершинных графов, попадающих в приближается к 1 при...
Комбинаторы взаимодействия были предложены в качестве цели компиляции для λ-исчисления ранее. Эта статья реализует полное λ-исчисление. Известно также, что можно оптимизировать кодировки сети взаимодействия λ-исчисления для подмножества λ-членов, которое можно типом EAL. Эта статья реализует это...
Теорема Борсука-Улама говорит, что для любой непрерывной нечетной функции из n-сферы в евклидово n-пространство существует точка такая, что .х 0 г ( х 0 ) = 0гggИкс0x0x_0г( х0) = 0g(x0)=0g(x_0)=0 Simmons и Su (2002) описывают метод аппроксимации точки с использованием леммы Такера . Однако не ясно,...
На сайте http://www.dharwadker.org/tevet/isomorphism/ представлен алгоритм определения изоморфности двух графов. Учитывая ряд, скажем так, «интересных» утверждений А. Дхарвадкера, я не склонен верить в это. В моем исследовании я обнаружил, что алгоритм определенно даст правильный ответ и скажет...
Следующий λ-член здесь в нормальной форме: sort = (λabc.(a(λdefg.(f(d(λhij.(j(λkl.(k(λmn.(mhi))l)) (h(λkl.l)i)))(λhi.(i(λjk.(bd(jhk)))(bd(h(λjk.(j (λlm.m)k))c)))))e))(λde.e)(λde.(d(λfg.g)e))c)) Реализует алгоритм сортировки для церковно-закодированных списков. То есть результат: sort (λ c n . (c 3...
Из статьи по стратегии оценки в Википедии: Понятие стратегии сокращения в лямбда-исчислении сходно, но различно. Из статьи о стратегии сокращения в Википедии: Это похоже на понятие стратегии оценки в информатике, но немного отличается от него. Какое тонкое различие между стратегиями оценки и...
Рассмотрим следующую проблему: Учитывая матрицу мы хотим оптимизировать количество сложений в алгоритме умножения для вычисления v ↦ M v .MMMv↦Mvv↦Mvv \mapsto Mv Я нахожу эту проблему интересной из-за ее связи со сложностью умножения матриц (эта проблема является ограниченным вариантом умножения...