В чем разница между логической структурой и теорией типов? Оба они имеют типы, термины и основаны на лямбда-исчислении с зависимой типизацией. У нас есть Edinburg LF, который основан на исчислении лямбда-пи, однако мне кажется, что здесь есть некоторая тонкая...
Для доказательства корректности я ищу пригодное для использования понятие эквивалентности программы для систем чистого типа (PTS) Барендрегта; не хватает этого, для достаточно специфических систем типов. Моя цель - просто использовать это понятие, а не исследовать его ради самого себя.≅≅\cong Это...
Я думал о том, к какому классу принадлежит этот язык: - граф, - натуральное число, а - хроматическое числоL = { ⟨ G , к ⟩ | GLзнак равно{⟨грамм,К⟩|граммL =\{ \langle G,k \rangle \mid G ККkККkG }грамм}G\} Я думал о как (1) «нет раскраски k-1 цветов» и (2) «есть раскраска цветов». Теперь (1) - это...
Обратная функция Аккермана часто встречается при анализе алгоритмов. Отличная презентация здесь: http://www.gabrielnivasch.org/fun/inverse-ackermann . α1(n)=[n/2]α1(n)=[n/2]\alpha_1(n) = [n/2] α2(n)=[log2n]α2(n)=[log2n]\alpha_2(n) = [\log_2 n] α3(n)=log∗nα3(n)=log∗n\alpha_3(n) = \log^* n...
Большинство теорий типов, которые мне известны, являются предикативными, под которыми я подразумеваю, что Void : Prop Void = (x : Prop) -> x не является типизированным в большинстве доказательств теорем, поскольку этот тип пи принадлежит той же вселенной, что Propи не тот случай Prop : Prop. Это...
Когда я смотрю на разбор Эрли, он выглядит очень элегантно, и мне интересно, почему методы GLR становятся популярными? Кто-нибудь знает, что не так с парсингом Эрли, который Томита создал GLR? Представление? Любые публикации по этой дискуссии высоко...
Я аспирант в области теоретических компьютерных наук, и в частности, алгоритмы аппроксимации. Теперь я нахожу, что меня больше интересует чистая математика (я могу сказать это, потому что мне, кажется, нравятся курсы математики больше, чем курсы CS). Я хотел бы спросить, есть ли области...
Есть алгоритмическая теория графов / теория чисел / комбинаторика / теория информации / теория игр. Есть ли алгоритмический математический анализ? Согласно вики, математический анализ включает в себя теории дифференцирования, интегрирования, измерения, пределов, бесконечных рядов и аналитических...
Для заданного набора гиперплоскостей, определяемых нормальными векторами , его типами ячеек (или знаковыми векторами) являются все векторы t ∈ { + , - } m, для которых существует вектор v ∈ R d так , что ⟨ v , ч я ⟩ ≠ 0 и т я = знак ( ⟨ v , ч я ⟩ )h1,…,hm∈Rdh1,…,hm∈Rdh_1,\dots,h_m \in \mathbf...
Мне было интересно, каков список текущих естественных вычислительных проблем, для которых нет никакого известного преимущества в сложности при использовании квантового компьютера. Прежде всего, я думаю, что вычисление расстояния редактирования - это то, для которого самый быстрый из известных...
Является ли теория типов Мартина-Лёфа в основном предикативным исчислением индуктивных конструкций без предиктивного ?П р о пProp\mathtt{Prop} Если они тесно связаны , но с большим количеством различий , чем просто , каковы эти различия?П р о...
Есть ли известный результат по классу сложности 1-в-3-SAT с ограниченным числом вхождений переменных? Я придумал следующее экономное сокращение с Питером Найтингейлом, но я хочу процитировать кое-что, если это известно. Вот трюк, который мы придумали. Это показывает, что 1-в-3-SAT, ограниченный...
Короче говоря, вопрос заключается в следующем: в какой степени вычислительные способности для сложных задач действительно помогают вам в решении простых задач. (Могут быть разные способы сделать этот вопрос интересным и нетривиальным, и вот одна из таких попыток.) Вопрос 1: Рассмотрим схему решения...
Зафиксируем конечную группу . Меня интересует следующая проблема решения: входными данными являются некоторые элементы группы с частичным порядком на них, и вопрос заключается в том, существует ли перестановка элементов, которая удовлетворяет порядку и такова, что композиция элементов в этом...
Учитывая ДАГ (ориентированный ациклический граф) , с источником S и раковины T . Найдите DAG D ′ с источниками S и приемниками T с минимальным количеством ребер таким образом, чтобы:DDDSSSTTTD'D′D'SSSTTT Для всех пар существует путь от u до v в D тогда и только тогда, когда существует путь от u до...
Учитывая , таким образом, что коэффициенты р , д ограничены B , имеет р ≡ Q удержание ?p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]p,qp,qp,qBBBp≡qp≡qp\equiv q Здесь применима лемма Шварца-Циппеля, поскольку она...
В проектах Polymath большая группа работает над открытой проблемой. Какие проблемы лучше всего работают в этих рамках? Есть ли хорошие кандидаты для участия в проекте по математике в теоретической информатике? Существуют ли какие-либо препятствия, которые делают проекты Polymath менее успешными в...
Недавно я наткнулся на статью Кудрона и Юена о расширении случайности с использованием квантовых устройств. Основным результатом работы является то, что можно генерировать «бесконечную» случайность из постоянного числа источников (то есть количество генерируемых случайных битов зависит только от...
Я экспериментирую с системами чистого типа в лямбда-кубе Барендрегта, особенно с наиболее мощным, исчислением конструкций. Эта система имеет сорта *и BOX. Для справки ниже я использую конкретный синтаксис Morteинструмента https://github.com/Gabriel439/Haskell-Morte-Library, который близок к...
В противоположной формуле CNF с двойным чтением каждая переменная появляется дважды, один раз положительный и один раз отрицательный. Меня интересует проблема , которая заключается в вычислении четности числа удовлетворяющих назначений противоположной формуле CNF с .⊕...