Несколько лет назад Джоэл Фридман сделал несколько работ, касающихся нижних границ цепей для когомологий Гротендика (см. Документы: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024. ). Принесло ли это направление мысли новое понимание булевой сложности, или это скорее...
Мы «знаем», что назван в честь Стива Кука, а назван в честь Ника Пиппенгера. Если я не ошибаюсь, Стив Кук назвал NC в честь Ника Пиппенджера, и мне сказали, что обратное также верно. Однако я не смог найти никаких доказательств этого последнего факта ни в статье Стива Кука о DCFL, ни в...
У меня очень сильная база в алгебре, а именно коммутативная алгебра, гомологическая алгебра, теория поля, теория категорий, и я в настоящее время изучаю алгебраическую геометрию. Я - математик со склонностью переключаться на теоретическую информатику. Помня вышеупомянутые области, какое поле было...
Рассмотрение вопросов через алгоритмическую линзу (то есть с алгоритмической или сложной точки зрения) стало полезным в дисциплинах вне «стандартной области» информатики. В частности, CS оказал влияние на биологию с помощью вычислительной биологии, на физику с помощью квантовой обработки...
Определите LOGLOG как класс языков, которые можно вычислить в пространстве O (loglog n) с помощью детерминированной машины Тьюринга (с двусторонним доступом к входу). Аналогично определите NLOGLOG как класс языков, которые могут быть вычислены в пространстве O (log log n) недетерминированной...
Этот вопрос касается проблем, для которых существует большой открытый разрыв сложности между известной нижней границей и верхней границей, но не из-за открытых проблем самих классов сложности. Чтобы быть более точным, скажем, у проблемы есть классы промежутков A,BA,BA,B (с , не определенным...
Существует часто цитируемое философское обоснование полагать, что P! = NP даже без доказательств. Другие классы сложности имеют доказательства того, что они различны, потому что если нет, то будут «удивительные» последствия (например, крах полиномиальной иерархии). Мой вопрос: на чем основано...
У меня есть некоторый опыт в научных вычислениях, и я широко использовал kd-деревья для приложений BSP (разбиение двоичного пространства). Недавно я стал более знаком с октреями, схожей структурой данных для разделения трехмерных евклидовых пространств, но той, которая работает с фиксированными...
В этом вопросе формула 3CNF означает формулу CNF, в которой каждое предложение включает ровно три различные переменные. Для константы 0 < s <1 Gap-3SAT s является следующей проблемой обещания: GAP-3sat сек экземпляра : а 3CNF формула φ. Да-обещание : φ выполнимо. Нет-обещание : Нет истину...
Я иногда слышал, как люди говорят о квантовых алгоритмах, о состояниях и о способности рассматривать несколько возможностей одновременно, но мне так и не удалось найти кого-то, кто мог бы объяснить вычислительную модель, стоящую за этим. Чтобы было ясно, я не спрашиваю о том, как физически...
В статье «Гипотеза случайного оракула ложна» авторы (Чанг, Чор, Гольдрайх, Хартманис, Хостад, Ранджан и Рохатхи) обсуждают значение гипотезы о случайном оракуле . Они утверждают, что мы очень мало знаем о разделениях между классами сложности, и большинство результатов включают либо использование...
Существует ли структура данных очереди с приоритетами, которая поддерживает следующие операции? Вставить (x, p) : добавить новую запись x с приоритетом p StableExtractMin () : возвращает и удаляет запись с минимальным приоритетом, разрывая связи по порядку вставки . Таким образом, после вставки (a,...
Два общих предположения для доказательства твердости результатов аппроксимации - это и гипотеза об уникальных играх. Есть ли какая-либо сложность результатов аппроксимации, предполагающих ? Я ищу проблему такую, что «трудно приблизить пределах коэффициента если ».N P ≠ c o N P A A α N P = c o N Pп≠...
Отказ от ответственности: я могу поручиться только за свои области исследований, а именно формальные методы, семантику и теорию языка программирования. Ситуация, возможно, отличается в других частях дисциплины. Кажется, что TCS стал скорее ориентированным на конференции. Исследователи стремятся...
Несмотря на то, что я прошел несколько курсов по теории вероятностей, как в старшей школе, так и в университете, мне трудно читать документы TCS, когда речь идет о вероятности. Кажется, что авторы работ TCS очень знакомы с вероятностью. Они волшебным образом работают с формулами вероятности и очень...
Мне нужна книга по теории конечных автоматов с множеством примеров, которые я могу использовать для самостоятельного изучения и подготовки к
В духе некоторых общих дискуссий, подобных этой , я открываю эту ветку с намерением собрать мнения о том, какие открытые проблемы и актуальные темы в исследованиях по языкам программирования . Я надеюсь, что обсуждение может даже привести к поверхностному мнению относительно будущего исследований в...
Невозможно написать язык программирования, который позволяет всем машинам, которые останавливаются на всех входах, и никаким другим. Тем не менее, кажется, что легко определить такой язык программирования для любого стандартного класса сложности. В частности, мы можем определить язык, на котором мы...
Я новичок в области CS и заметил, что во многих прочитанных мной документах нет эмпирических результатов (нет кода, только леммы и доказательства). Почему это? Учитывая, что информатика - это наука, разве она не должна следовать научному...
Существует ли обратная граница Черноффа, определяющая, что вероятность хвоста хотя бы так велика? т.е. если являются независимыми биномиальными случайными переменными и . Тогда мы можем доказать для некоторой функции...