Теорема Банаха о неподвижной точке говорит, что если у нас есть непустое полное метрическое пространство , то любая равномерно сжимающая функция имеет единственную неподвижную точку . Однако доказательство этой теоремы требует аксиомы выбора - нам нужно выбрать произвольный элемент чтобы начать...
Если у нас есть большой (направленный) граф и меньшее корневое дерево , какова наиболее известная сложность для нахождения подграфов группы изоморфных ? Мне известны результаты для изоморфизма поддеревьев, где и являются деревьями, а также где плоская или имеет ограниченную ширину дерева (и...
Что такое хорошие статьи / книги, чтобы лучше понять силу модульного разложения и его свойства? Я особенно заинтересован в алгоритмических аспектах модульной декомпозиции. Я слышал, что можно найти модульную декомпозицию графа за линейное время. Есть ли относительно простой алгоритм для этого? А...
Это написано в вики-записи Символического Выполнения , но я не могу найти для этого никакой ссылки. Кто-нибудь может показать мне указатель?
У меня на самом деле есть два вопроса: Кто первым использовал логические отношения, чтобы связать семантику? Я проследил их до Рейнольда « О связи между прямой и семантикой продолжения », но я не могу утверждать, что провел исчерпывающий поиск. Я нашел ссылки на логические отношения, датирующиеся...
Я использую заглавный термин в очень свободном смысле. Существует значительный объем работ по эволюционной теории игр, включая ее математические основы. Мне порекомендовали «Эволюционные игры и динамика населения», но я еще не углубился в это. Существует также значительный объем работ по теории...
Известно, что минимизация размера регулярного выражения является PSPACE-полной, даже если у нас есть DFA в качестве спецификации языка . Каковы результаты, если язык конечен? Можно рассмотреть эту проблему в двух моделях: Входные данные - это все строки в языке, и мы измеряем размер ввода как сумму...
Изменить: Поскольку я не получил никаких ответов / комментариев в течение недели, я хотел бы добавить, что я рад услышать что-нибудь о проблеме. Я не работаю в этом районе, поэтому, даже если это простое наблюдение, я могу не знать его. Даже комментарий типа «Я работаю в этом районе, но я не видел...
Категория имеет бипродукты, когда одни и те же объекты являются как продуктами, так и копроизведениями. Кто-нибудь исследовал теорию доказательств категорий с бипродуктами? Возможно, наиболее известным примером является категория векторных пространств, в которой конструкции прямой суммы и прямого...
С учетом множество и , A бифункционального соотношение между ними определяются как отношение , удовлетворяющее следующее свойство:B ( ∼ ) ⊆ A × BAAAВВB (∼)⊆A×B(∼)⊆A×B(\sim) \subseteq A \times B Если и a ′ ∼ b ′ и a ∼ b ′ , то a ′ ∼ b . a∼ba∼ba \sim ba′∼b′a′∼b′a' \sim b'a∼b′a∼b′a \sim b'a′∼ba′∼бa'...
Обозначим через множество а через C (n, k) - множество всех комбинаций элементов из без повторения. Пусть - k- кортеж в C (n, k) . Мы говорим, что перестановка \ pi: [n] \ rightarrow [n] из набора [n] избегает p, если нет k-кортежа целых чисел i_1 <i_2 <... <i_k, такого что \ pi (i_1) =...
Какова наиболее известная сложность запроса алгоритма обучения Голдрайха-Левина? Лекционные заметки из блога Лука Тревисан в , леммы 3, утверждает его как . Это самый известный с точки зрения зависимости от п ? Буду особенно благодарен за ссылку на цитируемый источник!O ( 1 / ϵ4журнал nн...
вычислительная сложность включает в себя большое количество комбинаторики и теории чисел, некоторые особенности стохастики и растущее количество алгебры. Однако, будучи аналитиком, мне интересно, есть ли приложения анализа в этой области, или, может быть, идеи, вдохновленные анализом. Все, что я...
Справочная информация : Я заканчиваю магистратуру по математике и в августе начну работу над докторской диссертацией по логике. Чем больше логики я изучаю, тем больше теоретической информатики, с которой я сталкиваюсь, например, теория рекурсии, лямбда-исчисление, но лежащий в основе CS лежит под...
Рассмотрим мерное пространство , и пусть - линейное ограничение вида , где , и k \ in \ mathbb {R} .nnn{0,1}n{0,1}n\{0,1\}^nccca1Икс1+ а2Икс2+ а3Икс3+ . , , + а n - 1Иксn - 1+ аNИксN≥ ka1x1+a2x2+a3x3+ ... +an−1xn−1+anxn≥ka_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq kaя∈ Rai∈Ra_i...
Рассмотрим следующий естественный вопрос: для какого конечного языка наименьшая не зависящая от контекста грамматика порождает L ?LLLLLL Мы можем сделать вопрос более интересным, указав последовательность языков , например, L n - это множество всех перестановок { 1 , … , n } : интуитивно, CFG для L...
GI и проблема узлов являются проблемой определения структурной эквивалентности математических объектов. Есть ли какие-либо результаты установления связей между ними? Хорошие связи проблемы узлов со статистической физикой были изучены с помощью полиномов узлов , есть ли похожие результаты для ?G...
Какой класс сложности связан с исчерпывающими алгоритмами поиска? (если есть) Это NP или PSPACE? Существуют ли ограниченные модели вычислений, охватывающие класс алгоритмов исчерпывающего поиска, аналогичных моделям для жадного и динамического...
Как все знают, SAT завершен для сравнению с многозначным сокращением за полиномиальное время. Это все еще полные сокращения wrt много-один.NPNP\mathsf{NP}AC0AC0\mathsf{AC^0} Мои вопросы: какова минимальная необходимая глубина для сокращений? Более формально, Что наименьшее такое, что SAT - это...
Я начинаю свою докторскую диссертацию этой осенью и планирую работать над теорией сложности для своей диссертации. Я составляю список важных работ, которые должен знать каждый теоретик сложности. Какие документы вы бы предложили человеку, как я? И, пожалуйста, кратко объясните, почему вы считаете...