Недавно я обнаружил квадратичную нижнюю границу сложности задачи в модели дерева решений, и мне интересно, можно ли частично обобщить этот результат в модели машины с произвольным доступом. Под частичностью я подразумеваю обобщение программ ОЗУ с определенным временным / пространственным...
Читая статью « Аппликативная теория для FPH », вы можете встретить следующий отрывок: Рассматривая теории, которые характеризуют классы вычислительной сложности, существует три разных подхода: в одном функции, которые могут быть определены в рамках теории, «автоматически» находятся в определенном...
Предположим, мы имеем дело с языком программирования, который поддерживает линейные типы (термины линейного типа можно использовать не более одного раза, так сказать). Это позволяет обрабатывать некоторые вычислительные эффекты (такие как мутация, даже изменение типа операнда) способом, который...
Как всем известно, знаменитая книга Гэри и Джонсона (и многие другие) дает превосходный справочник по технике редукции в классической обстановке. Существуют ли какие-либо обзоры или книги на тему техники редукции в параметризованном алгоритме, скажем, редукция...
Я задал этот вопрос о переполнении стека некоторое время назад: Проблема: продажа Боба . Кто-то предложил также разместить здесь вопрос. Кто-то уже задавал вопрос, связанный с этой проблемой, здесь - минимальный вес леса данной мощности - но, насколько я понимаю, это не помогает мне с моей...
Учитывая матрицу m×nm×nm \times n (при условии, что m≥nm≥nm \ge n ), каков самый быстрый алгоритм для вычисления его ранга и базиса столбцов? Я знаю, что это может быть решено с помощью линейного пересечения матроидов, что подразумевает детерминистический алгоритм времени...
Я ищу статьи и статьи о модальных субструктурных логиках - не о семантике линейных логических модальностей, а о субструктурных логиках, дополненных стандартными модальными операторами, например, субструктурными K (что-то вроде MALL с оператором ящика, необходимостью и K...
Теорема Банаха о неподвижной точке говорит, что если у нас есть непустое полное метрическое пространство , то любая равномерно сжимающая функция имеет единственную неподвижную точку . Однако доказательство этой теоремы требует аксиомы выбора - нам нужно выбрать произвольный элемент чтобы начать...
Что такое хорошие статьи / книги, чтобы лучше понять силу модульного разложения и его свойства? Я особенно заинтересован в алгоритмических аспектах модульной декомпозиции. Я слышал, что можно найти модульную декомпозицию графа за линейное время. Есть ли относительно простой алгоритм для этого? А...
Наезд набор из семейства является подмножеством из такое , что для . Задача найти минимальное множество попаданий данного семейства NP-трудна в общем, поскольку она обобщает проблему покрытия вершин. Теперь мой вопрос:S= { S1, … , SN}Sзнак равно{S1,...,SN}\mathcal{S} = \{S_1, \dots, S_n\}ЧАСЧАСH⋃Nя...
(Обобщенная) высота звезды в языке - это минимальная вложенность звезд Клини, необходимая для представления языка расширенным регулярным выражением. Напомним, что расширенное регулярное выражение над конечным алфавитом удовлетворяет следующему:AAA (1) и - расширенные регулярные выражения для...
Я пытаюсь понять некоторые понятия о модульной декомпозиции и графах ширины клика . В этой статье («О P4-аккуратных графах») есть доказательство того, как решать задачи оптимизации, такие как число кликов или хроматическое число, с использованием модульной декомпозиции. Решение этих проблем путем...
Дефункционализация - это программная трансформация, которая преобразует программы высшего порядка в программы первого порядка. Идея состоит в том, что для данной программы существует только конечное число лямбда-абстракций, поэтому вы можете заменить каждую лямбду идентификатором, а каждое...
Фон Функции в могут быть изучены PAC в квазиполиномиальном времени с помощью классического алгоритма, который требует случайно выбранных запросов, чтобы изучить схему глубины d [1]. Если нет факторинг-алгоритма , то это оптимально [2]. Конечно, на квантовом компьютере мы знаем, как учитывать,...
Не могли бы вы указать, как построить функцию Аккермана (на самом деле меня интересует версия, предложенная Роузой Петером и Рафаэлем Робинсоном) с помощью стандартных мюрекурсивных операторов? Я пробовал оригинальные статьи Петера и Робинсона, но в работе Петера используется язык, отличный от...
У меня на самом деле есть два вопроса: Кто первым использовал логические отношения, чтобы связать семантику? Я проследил их до Рейнольда « О связи между прямой и семантикой продолжения », но я не могу утверждать, что провел исчерпывающий поиск. Я нашел ссылки на логические отношения, датирующиеся...
Я использую заглавный термин в очень свободном смысле. Существует значительный объем работ по эволюционной теории игр, включая ее математические основы. Мне порекомендовали «Эволюционные игры и динамика населения», но я еще не углубился в это. Существует также значительный объем работ по теории...
Из теоремы универсального приближения известно, что нейронная сеть с хотя бы одним скрытым слоем и произвольной функцией активации может аппроксимировать любую непрерывную функцию. Какие есть еще модели, которые также являются универсальными аппроксиматорами...
Категория имеет бипродукты, когда одни и те же объекты являются как продуктами, так и копроизведениями. Кто-нибудь исследовал теорию доказательств категорий с бипродуктами? Возможно, наиболее известным примером является категория векторных пространств, в которой конструкции прямой суммы и прямого...
Задача обслуживания заказа (или «поддержание заказа в списке») заключается в поддержке операций: singleton: создает список с одним элементом, возвращает указатель на него insertAfter: дает указатель на элемент, вставляет новый элемент после него, возвращает указатель на новый элемент delete: дает...