Существуют некоторые проблемы подсчета, которые включают экспоненциальный подсчет многих вещей (относительно размера входных данных), и в то же время имеют удивительные точные, детерминированные алгоритмы за полиномиальное время. Примеры включают в себя: Подсчет идеальных совпадений в плоском графе...
В описательной сложности Иммерман имеет Следствие 7.23. Следующие условия эквивалентны: 1. P = NP. 2. Над конечными упорядоченными структурами FO (LFP) = SO. Это можно рассматривать как «усиление» P = NP до эквивалентного утверждения над (предположительно) классами большей сложности. Обратите...
Какие ваши любимые примеры, когда теория информации используется, чтобы доказать аккуратное комбинаторное утверждение простым способом? Некоторые примеры, которые я могу придумать, связаны с нижними границами для локально декодируемых кодов, например, в этой статье: предположим, что для двоичных...
Это мой первый вопрос на этом сайте. Я учусь в магистратуре по теории вычислений. Как бы вы объяснили проблему P = NP 10-летнему ребенку и почему он получил такое денежное вознаграждение? Твой дубль? Я обновлю вопрос, когда моя голова прояснит...
Предположим, что и G 2 являются двумя неориентированными графами на множестве вершин { 1 , … , n } . Графы изоморфны тогда и только тогда, когда существует перестановка Π такая, что G 1 = Π ( G 2 ) , или более формально, если существует перестановка Π такая, что ( i , j ) является ребром в G 1...
Многие первоклассные исследователи в области компьютерных наук и исследовательские группы) ведут активные блоги, которые держат нас в курсе последних исследований в областях, представляющих интерес для авторов. В большинстве случаев посты в блоге легче понять, чем формальные документы, потому что в...
Мой доктор философии в чистой математике, и я признаю, что я не знаю много (то есть ничего) о теоретической CS. Однако я начал изучать неакадемические варианты своей карьеры и, знакомясь с машинным обучением, наткнулся на утверждения типа «Никто не понимает, почему нейронные сети работают хорошо»,...
Рассмотрим непересекающихся семейств подмножеств {1,2,…, n}, F 1 , F 2 , … F t .TttF1, F2, … FTF1,F2,…Ft{\cal F}_1,{\cal F_2},\dots {\cal F_t} Предположим, что (*) Для каждого , и каждый R ∈ F я и Т ∈ F к , существует S ∈ F J , который содержит R ∩ T .я < J < Ki<j<ki \lt j \lt kR ∈...
Два способа анализа эффективности алгоритма: поставить асимптотическую верхнюю границу времени выполнения и запустить его и собрать экспериментальные данные. Интересно, известны ли случаи, когда между (1) и (2) существует значительный разрыв. Под этим я подразумеваю, что либо (а) экспериментальные...
Для (поисковых версий) NP- неполных задач проверить решение явно проще, чем найти его, поскольку проверка может быть выполнена за полиномиальное время, тогда как поиск свидетеля занимает (вероятно) экспоненциальное время. Однако в P решение также может быть найдено за полиномиальное время, поэтому...
Меня часто спрашивают, чем занимается теоретический компьютерщик. Было бы здорово получить хорошие ответы на этот вопрос. Я склонен прибегать к техническому жаргону, и в этот момент глаза людей обычно застекляются. Что делает теоретический компьютерный ученый в терминах, которые могут понять люди,...
Этот вопрос вдохновлен другим вопросом о том, что нового в ПФДС с момента публикации книги Окасаки в 1998 году . Я начну с двух вопросов, которые у меня есть: Существует ли чисто функциональная структура данных набора, которая приближается к скорости хеш-таблиц? Попытки еще не там. Существуют ли...
После плодотворного вопроса в МО , я подумал, что стоит обсудить некоторые заметные названия статей в CS. Совершенно очевидно, что большинству из нас может быть интересно прочитать (или хотя бы взглянуть) статью с интересным названием (по крайней мере, я делаю это каждый раз, когда просматриваю...
В своей знаменитой статье «Сопряженное кодирование» (написано около 1970 года) Стивен Виснер предложил схему для квантовых денег, которую безоговорочно невозможно подделать, предполагая, что банк-эмитент имеет доступ к гигантской таблице случайных чисел и что банкноты могут быть принесены обратно в...
Есть ли связь между машиной Тьюринга и лямбда-исчислением - или они просто возникли примерно в одно и то же
Это может быть субъективный вопрос, а не конкретный ответ, но в любом случае. В теории сложности мы изучаем понятие эффективных вычислений. Существуют классы, такие как обозначает полиномиальное время , а обозначает пространство журнала . Оба они считаются своего рода «эффективностью», и они...
У меня есть три связанных подвопроса, которые выделены пунктами ниже (нет, их нельзя разделить, если вам интересно). Андрей Бауэр писал здесь , что некоторые функции реализуются через машину Тьюринга, но не через лямбда-исчисление. Ключевой шаг его рассуждений: Однако, если мы используем...
Известно, что некоторые проблемы неразрешимы, но, тем не менее, можно добиться определенного прогресса в их решении. Например, проблема остановки неразрешима, но можно добиться практического прогресса в создании инструментов для обнаружения потенциальных бесконечных циклов в вашем коде. Проблемы с...
Функциональное программирование имеет теоретическую основу в лямбда-исчислении и комбинаторной логике . Как человек, занимающийся статистическими вычислениями, я нахожу эти концепции очень полезными для моделирования. Существует ли эквивалентная математическая основа императивного программирования...
Теория сложности - мой сильный вторичный интерес, но это не мой основной исследовательский интерес, поэтому у меня нет надежды посетить все конференции, прочитать все блоги и убедиться, что толпа «в» cc: me на каждом кусочке горячие новости. Я пытаюсь сделать что-то из этого, но мне интересно,...