вычислительная сложность включает в себя большое количество комбинаторики и теории чисел, некоторые особенности стохастики и растущее количество алгебры. Однако, будучи аналитиком, мне интересно, есть ли приложения анализа в этой области, или, может быть, идеи, вдохновленные анализом. Все, что я...
Рассмотрим следующий естественный вопрос: для какого конечного языка наименьшая не зависящая от контекста грамматика порождает L ?LLLLLL Мы можем сделать вопрос более интересным, указав последовательность языков , например, L n - это множество всех перестановок { 1 , … , n } : интуитивно, CFG для L...
Я хочу узнать об алгебраических алгоритмах и их сложности. В частности, меня интересует PIT. Есть ли набор лекций, книг, статей и опросов для студентов, которые читали стандартный учебник по теории, такой как книга Сипсера или учебник по сложности Арора-Барака. Набор ссылок будет включать в себя...
Пусть G будет ненаправленным графом из n узлов, и пусть T будет подмножеством узлов V (G), называемых терминалами . Сохранитель расстояния (G, T) - это граф H, удовлетворяющий свойству dЧАС( u , v ) = dграмм( ты , ты )dЧАС(U,v)знак равноdграмм(U,v)d_H(u,v) = d_G(u,v) для всех узлов u, v в T....
Будучи студентом, изучающим информатику, я познакомился с теорией игр, но не видел подробностей по этому вопросу. Я искал в Google и просмотрел несколько книг по теории игр, и они предоставили подтверждение ее использования в информатике. Я начал формальное изучение теории игр с точки зрения...
Я начинаю свою докторскую диссертацию этой осенью и планирую работать над теорией сложности для своей диссертации. Я составляю список важных работ, которые должен знать каждый теоретик сложности. Какие документы вы бы предложили человеку, как я? И, пожалуйста, кратко объясните, почему вы считаете...
(уже просили на главном сайте , но просим также о лучшем освещении, извините) Так как я знал о сжатых структурах данных, мне отчаянно нужен хороший обзор последних событий в этой области. Я погуглил и прочитал много статей, которые я мог видеть в верхней части результатов Google по запросам сверху...
Я готовлю некоторые учебные материалы по эвристике для оптимизации и изучаю методы координатного спуска. Здесь настройка представляет собой многовариантную функцию которую вы хотите оптимизировать. f имеет свойство, ограниченное какой-либо одной переменной, его легко оптимизировать. Таким образом,...
Я вспоминаю, как видел исследование или статью, где недавно утверждалось, что большая часть ускорения, наблюдаемого в компьютерных программах за последние несколько десятилетий, происходит от более совершенных алгоритмов, а не от более быстрого аппаратного обеспечения. Кто-нибудь знает исследование...
GI и проблема узлов являются проблемой определения структурной эквивалентности математических объектов. Есть ли какие-либо результаты установления связей между ними? Хорошие связи проблемы узлов со статистической физикой были изучены с помощью полиномов узлов , есть ли похожие результаты для ?G...
Какова наиболее известная сложность запроса алгоритма обучения Голдрайха-Левина? Лекционные заметки из блога Лука Тревисан в , леммы 3, утверждает его как . Это самый известный с точки зрения зависимости от п ? Буду особенно благодарен за ссылку на цитируемый источник!O ( 1 / ϵ4журнал nн...
Какой класс сложности связан с исчерпывающими алгоритмами поиска? (если есть) Это NP или PSPACE? Существуют ли ограниченные модели вычислений, охватывающие класс алгоритмов исчерпывающего поиска, аналогичных моделям для жадного и динамического...
Справочная информация : Я заканчиваю магистратуру по математике и в августе начну работу над докторской диссертацией по логике. Чем больше логики я изучаю, тем больше теоретической информатики, с которой я сталкиваюсь, например, теория рекурсии, лямбда-исчисление, но лежащий в основе CS лежит под...
Как все знают, SAT завершен для сравнению с многозначным сокращением за полиномиальное время. Это все еще полные сокращения wrt много-один.NPNP\mathsf{NP}AC0AC0\mathsf{AC^0} Мои вопросы: какова минимальная необходимая глубина для сокращений? Более формально, Что наименьшее такое, что SAT - это...
Я внедряю некоторую системную часть, которая требует некоторой помощи. Поэтому я формулирую это как проблему графа, чтобы сделать его независимым от домена. Задача: Нам дан ориентированный ациклический граф . Без ограничения общности предположим, что G имеет ровно одну исходную вершину s и ровно...
Рассмотрим мерное пространство , и пусть - линейное ограничение вида , где , и 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...
Недавно я узнал о гипотезе Жадности о самой короткой проблеме суперструн . В этой задаче нам дан набор строк и мы хотим найти самую короткую суперструну то есть такую, чтобы каждая как подстрока .s1,…,sns1,…,sns_1,\dots, s_n ssssisis_isss Эта задача является NP-трудной, и после длинной серии работ...
При чтении вопрос примеров , где единственность решения делает его легче найти , новый (? Проще) возник вопрос , на мой взгляд: на самом деле мы не знаем , если Изоморфизм графов ( проблема) в .GIGIGIPPP Но что произойдет, если мы предположим, что обаG1G1G_1 и асимметричны (т.е. оба имеют только...
Фиксированный параметр и аппроксимация - это совершенно разные подходы для решения сложных задач. У них разная мотивация. Приближение ищет более быстрый результат с приближенным решением. Фиксированный параметр ищет точное решение с временной сложностью в терминах экспоненциальной или некоторой...
Хорошо известно, что сложность отличия монеты, смещенной на от монеты-монеты - это . Есть ли результаты для отличия монеты от монеты ? Я вижу, что для частного случая сложность будет . У меня есть догадка, что сложность будет зависеть от того, имеет ли порядок , но не может доказать это строго....