Существуют ли какие-либо предположения в теоретической информатике, которые включают некоторый параметр n и были доказаны для малых значений n AND для простых чисел, но позже оказались ложными? В теории чисел такие проблемы существуют, например. как Аарон Мейеровиц указывает на один из...
Я аспирант по математике с твердым опытом в логике. Я прошел годичный курс для выпускников по логике вместе с курсами для выпускников по теории конечных моделей и другим курсам по принуждению и теории множеств. Большинство текстов CS, кажется, предполагают только очень скромный фон в логике,...
Любая монада также является аппликативным функтором, а любой аппликативный функтор - функтором. Также любая комонада является функтором. Существует ли похожая концепция между комонадами и функторами, что-то вроде ко-аппликативного функтора, и каковы его свойства? \begin{array}{c} \end{array}...
Рассмотрим перестановку σσ\sigma из [1..n][1..n][1..n] . Инверсия определяется как пара (i,j)(i,j)(i, j) индексов, такая что i<ji<ji < j и σ(i)>σ(j)σ(i)>σ(j)\sigma(i) > \sigma(j) . Определите AkAkA_k как число перестановок в [1..n][1..n][1..n] с не более чем kkk инверсиями. Вопрос:...
Сложность схемы с ограниченной глубиной является одной из основных областей исследования в теории сложности схемы. Эта тема имеет происхождение в результатах типа «функция четности не в » и « функция mod не вычисляется », где - класс языков, разрешимых по неоднородности, постоянной глубине,...
В алгоритме Штрассена, чтобы вычислить произведение двух матриц и B , матрицы A и B делятся на блочные матрицы 2 × 2, и алгоритм продолжает рекурсивное вычисление 7- блочных матрично-матричных произведений, а не наивных 8- блочных матричных матриц. матричные произведения, т. е. если мы хотим C = A...
Я ищу естественные примеры эффективных алгоритмов (т.е. в полиномиальном времени) их правильность и эффективность могут быть доказаны конструктивно (например, в PRAпрAPRA или ), ноHAЧАСAHA не известно никаких доказательств, использующих только эффективные концепции (то есть мы не знаем, как...
Начиная с Curry-Howard-Lambek, было триединство теорий типов, логик и категорий. Мне любопытно, какую категоричную семантику вы получаете, когда добавляете (принудительный) подтип в теорию типов - кажется, что это не очень изучалось, если вообще. В целом, добавление коэрцитивного подтипирования в...
Недавно я столкнулся со следующим вариантом окраски краев. Для связного неориентированного графа найдите раскраску ребер, которая использует максимальное количество цветов, а также удовлетворяет ограничению, согласно которому для каждой вершины ребра, инцидентные используют не более двух...
Одна вещь, которую могут сделать квантовые компьютеры (возможно, даже с использованием только квантовых цепей с логарифмической глубиной BPP +), - это аппроксимировать выборку преобразования Фурье булевой -значной функции в P.± 1±1\pm 1 Здесь и ниже, когда я говорю о выборке преобразования Фурье, я...
Рассмотрим следующую задачу QQQ : Нам дано целое число и k интервалов [ l i , r i ] с 1 ≤ l i ≤ r i ≤ 2 n . Нам также даны 2 n целых чисел d 1 , … , d 2 n ≥ 0 . Задача состоит в том, чтобы выбрать минимальное количество интервалов [ l i , r i ]nnnkkk[li,ri][li,ri][l_i,r_i]1≤li≤ri≤2n1≤li≤ri≤2n1\leq...
При попытке убедить экономистов в актуальности теории сложности в печати, есть ли стандартная ссылка для цитирования? Я знаком с постом в блоге Ноама Нисана , опросом Тима Раугардена и 11-й статьей эссе Скотта Ааронсона . Эти посты доступны для компьютерных ученых, но не используют язык экономистов...
Известен ли следующий класс графов в литературе? Класс графов параметризуется натуральными числами и и содержит каждый граф такой, что для каждой вершины подграф индуцируется на всех вершинах на расстоянии не более от в имеет длину не более .dddTTtG = ( V, E)граммзнак равно(В,Е)G=(V,E)v ∈ Vv∈Вv\in...
Я делаю обзор литературы по проблеме изоморфизма графов. Большинство статей, которые я читаю, написаны Э. М. Луксом и Ласло Бабаи. В этих работах используются знания высокого уровня теории групп и теории сложности. Поскольку я новичок в этой области, многие вещи мне не понятны. Может кто-нибудь...
В настоящее время я учусь в средней школе, интересуюсь теоретической информатикой и прикладной математикой. Я сам учил себя линейной алгебре и исчислению и конкретной математике. У меня есть наивное представление о том, что для того, чтобы писать лучшие алгоритмы, нужно знать как можно больше...
Некоторая работа по чувствительности против чувствительности блоков была направлена на изучение функций с максимально большим промежутком между и , чтобы развить гипотезу, что только полиномиально больше, чем . Как насчет противоположного направления? Что известно о функциях, где...
Предположим, я рассматриваю следующий вариант BPP, который позволяет нам называть E (xact) BPP: язык находится в EBPP, если существует рандомизированный TG за полиномиальное время, который принимает каждое слово языка с вероятностью 3/4 и каждое слово не в язык с вероятностью 1/4. Очевидно, что...
При поиске Информационной системы о классах графов и их включениях я обнаружил несколько классов графов, для которых задача о гамильтоновом цикле NP-полна, а сложность задач о гамильтоновом пути НЕ известна. Некоторые из этих классов представляют собой двудольные графы максимальной степени 3,...
Следуя предложению Джоша Грохова, я превращаю свой комментарий из предыдущего вопроса в новый. Какие доказательства у нас есть для ?UP≠NPUP≠NP\mathsf{UP} \neq \mathsf{NP} Здесь - это класс языков, распознаваемых недетерминированными машинами Тьюринга за полиномиальное время, которые имеют...
Нижняя граница Блума 3n−o(n)3N-о(N)3n-o(n) - это лучшая известная нижняя граница схемы по полному базису для явной функции f:{0,1}n→{0,1}f:{0,1}n→{0,1}f : \{0,1\}^n \to \{0,1\} , ср. Юкна ответ на этот вопрос для связанных результатов. Каковы наиболее известные нижние оценки, если диапазон fff...