Вопросы с тегом «reference-request»

14
Математический анализ и вычислительная сложность?

вычислительная сложность включает в себя большое количество комбинаторики и теории чисел, некоторые особенности стохастики и растущее количество алгебры. Однако, будучи аналитиком, мне интересно, есть ли приложения анализа в этой области, или, может быть, идеи, вдохновленные анализом. Все, что я...

14
Нижние границы размера CFG для определенных конечных языков

Рассмотрим следующий естественный вопрос: для какого конечного языка наименьшая не зависящая от контекста грамматика порождает L ?LLLLLL Мы можем сделать вопрос более интересным, указав последовательность языков , например, L n - это множество всех перестановок { 1 , … , n } : интуитивно, CFG для L...

14
Курс обучения алгебраической сложности

Я хочу узнать об алгебраических алгоритмах и их сложности. В частности, меня интересует PIT. Есть ли набор лекций, книг, статей и опросов для студентов, которые читали стандартный учебник по теории, такой как книга Сипсера или учебник по сложности Арора-Барака. Набор ссылок будет включать в себя...

14
Существование планарного расстояния?

Пусть 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....

14
Приложения теории игр в информатике?

Будучи студентом, изучающим информатику, я познакомился с теорией игр, но не видел подробностей по этому вопросу. Я искал в Google и просмотрел несколько книг по теории игр, и они предоставили подтверждение ее использования в информатике. Я начал формальное изучение теории игр с точки зрения...

14
Статьи любой сложности теоретик должен прочитать

Я начинаю свою докторскую диссертацию этой осенью и планирую работать над теорией сложности для своей диссертации. Я составляю список важных работ, которые должен знать каждый теоретик сложности. Какие документы вы бы предложили человеку, как я? И, пожалуйста, кратко объясните, почему вы считаете...

14
Нужен хороший обзор для алгоритмов сжатой структуры данных

(уже просили на главном сайте , но просим также о лучшем освещении, извините) Так как я знал о сжатых структурах данных, мне отчаянно нужен хороший обзор последних событий в этой области. Я погуглил и прочитал много статей, которые я мог видеть в верхней части результатов Google по запросам сверху...

14
Теоретическое исследование методов координатного спуска

Я готовлю некоторые учебные материалы по эвристике для оптимизации и изучаю методы координатного спуска. Здесь настройка представляет собой многовариантную функцию которую вы хотите оптимизировать. f имеет свойство, ограниченное какой-либо одной переменной, его легко оптимизировать. Таким образом,...

14
Ускорение от алгоритмических достижений против аппаратного обеспечения

Я вспоминаю, как видел исследование или статью, где недавно утверждалось, что большая часть ускорения, наблюдаемого в компьютерных программах за последние несколько десятилетий, происходит от более совершенных алгоритмов, а не от более быстрого аппаратного обеспечения. Кто-нибудь знает исследование...

14
Подходы к GI, вдохновленные проблемой узлов

GI и проблема узлов являются проблемой определения структурной эквивалентности математических объектов. Есть ли какие-либо результаты установления связей между ними? Хорошие связи проблемы узлов со статистической физикой были изучены с помощью полиномов узлов , есть ли похожие результаты для ?G...

14
Наилучшая сложность запросов алгоритма обучения Голдрайха-Левина / Кушилевица-Мансура

Какова наиболее известная сложность запроса алгоритма обучения Голдрайха-Левина? Лекционные заметки из блога Лука Тревисан в , леммы 3, утверждает его как . Это самый известный с точки зрения зависимости от п ? Буду особенно благодарен за ссылку на цитируемый источник!O ( 1 / ϵ4журнал nн...

14
Класс сложности, связанный с исчерпывающим поиском

Какой класс сложности связан с исчерпывающими алгоритмами поиска? (если есть) Это NP или PSPACE? Существуют ли ограниченные модели вычислений, охватывающие класс алгоритмов исчерпывающего поиска, аналогичных моделям для жадного и динамического...

14
Ресурсы для математиков, надеющихся узнать больше информатики

Справочная информация : Я заканчиваю магистратуру по математике и в августе начну работу над докторской диссертацией по логике. Чем больше логики я изучаю, тем больше теоретической информатики, с которой я сталкиваюсь, например, теория рекурсии, лямбда-исчисление, но лежащий в основе CS лежит под...

14
Какова минимальная необходимая глубина снижения NP-твердости SAT?

Как все знают, SAT завершен для сравнению с многозначным сокращением за полиномиальное время. Это все еще полные сокращения wrt много-один.NPNP\mathsf{NP}AC0AC0\mathsf{AC^0} Мои вопросы: какова минимальная необходимая глубина для сокращений? Более формально, Что наименьшее такое, что SAT - это...

14
Точный алгоритм для задачи маркировки ребер в DAG

Я внедряю некоторую системную часть, которая требует некоторой помощи. Поэтому я формулирую это как проблему графа, чтобы сделать его независимым от домена. Задача: Нам дан ориентированный ациклический граф . Без ограничения общности предположим, что G имеет ровно одну исходную вершину s и ровно...

14
0-1 Линейное программирование: вычисление оптимальной формулировки

Рассмотрим мерное пространство , и пусть - линейное ограничение вида , где , и 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...

14
Почему жадная гипотеза так сложна?

Недавно я узнал о гипотезе Жадности о самой короткой проблеме суперструн . В этой задаче нам дан набор строк и мы хотим найти самую короткую суперструну то есть такую, чтобы каждая как подстрока .s1,…,sns1,…,sns_1,\dots, s_n ssssisis_isss Эта задача является NP-трудной, и после длинной серии работ...

13
Тестирование изоморфизма асимметричных графов

При чтении вопрос примеров , где единственность решения делает его легче найти , новый (? Проще) возник вопрос , на мой взгляд: на самом деле мы не знаем , если Изоморфизм графов ( проблема) в .GIGIGIPPP Но что произойдет, если мы предположим, что обаG1G1G_1 и асимметричны (т.е. оба имеют только...

13
Связь между фиксированным параметром и алгоритмом аппроксимации

Фиксированный параметр и аппроксимация - это совершенно разные подходы для решения сложных задач. У них разная мотивация. Приближение ищет более быстрый результат с приближенным решением. Фиксированный параметр ищет точное решение с временной сложностью в терминах экспоненциальной или некоторой...

13
Различение между двумя монетами

Хорошо известно, что сложность отличия монеты, смещенной на от монеты-монеты - это . Есть ли результаты для отличия монеты от монеты ? Я вижу, что для частного случая сложность будет . У меня есть догадка, что сложность будет зависеть от того, имеет ли порядок , но не может доказать это строго....