Я разрабатываю простой статически типизированный функциональный язык программирования для обучения. Похоже, что система типов, которую я реализовал до сих пор, могла (с небольшой дополнительной работой) включать типы пересечений и объединений, например, вы могли бы иметь: <Union String...
Я работал над внедрением некоторых результатов вычислительной сложности в теоретическую биологию, особенно эволюцию и экологию , с целью быть интересным / полезным для биологов. Одна из самых больших трудностей, с которыми я столкнулся, заключается в обосновании полезности асимптотического анализа...
все знают, что существует много проблем с решениями, которые являются NP-сложными на общих графах, но меня интересуют проблемы, которые даже NP-сложны, когда лежащий в основе граф является путем. Итак, вы можете помочь мне собрать такие проблемы? Я уже нашел связанный вопрос о NP-трудных проблемах...
Многие задачи алгоритмического графа могут быть решены за полиномиальное время как на невзвешенных, так и на взвешенных графах. Некоторыми примерами являются кратчайший путь, минимальное связующее дерево, самый длинный путь (в ориентированных ациклических графах), максимальный поток, минимальное...
Это своего рода открытый вопрос, за который я заранее прошу прощения. Существуют ли примеры утверждений, которые (казалось бы) не имеют ничего общего со сложностью или машинами Тьюринга, но ответ на них подразумевал бы ?P ≠ N PP≠NP\mathbf{P}\neq...
Исходя из предыдущего вопроса , Каковы наилучшие текущие нижние границы пространства для SAT? С нижней границей пробела здесь я имею в виду количество ячеек рабочей ленты, используемых машиной Тьюринга, которая использует двоичный алфавит рабочей ленты. Постоянный аддитивный член неизбежен,...
В статье Томаса Дж. Шефера « Сложность проблем с удовлетворенностью» автор упомянул, что This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the relational complexity...
Я читал, что изначально Черч предложил -calculus как часть своей статьи «Постулаты логики» (которая читается плотно). Но Клини доказал свою «систему» непоследовательной, после чего Черч извлек соответствующие вещи для своей работы по «эффективной вычислимости» и отказался от своей предыдущей...
Для рандомизированных алгоритмов AA\mathcal{A} принимающих реальные значения, «срединный трюк» - это простой способ уменьшить вероятность отказа до любого порогового значения δ>0δ>0\delta > 0 , за счет только мультипликативного t=O(log1δ)t=O(log1δ)t=O(\log\frac{1}{\delta})накладные расходы....
Я читал статью Андрея Бауэра « Первые шаги в теории синтетической вычислимости» . В заключении он отмечает, что Наша аксиоматизация имеет свой предел: она не может доказать какие-либо результаты в теории вычислимости, которые не могут относиться к вычислениям оракула. Это так, потому что теория...
В этой теме попытка Нобетта Блюма в доказательстве лаконично опровергается, когда отмечается, что функция Тардоса является контрпримером к теореме 6P≠NPP≠NPP \neq NP Теорема 6 : Пусть - любая монотонная булева функция. Предположим, что существует CNF-DNF-аппроксиматор который можно использовать для...
Пусть переменные будут Икс1, х2, х3, , , ИксNИкс1,Икс2,Икс3,,,ИксNx_1 , x_2 , x_3 ... x_n . Расстояние между двумя переменными определяется как d( хa, хб) = | а - б |d(Иксa,Иксб)знак равно|a-б|d(x_a , x_b) = |a-b|, Расстояние между двумя литералами - это расстояние между соответствующими двумя...
Существует ли хороший опрос, в котором сравниваются различные экстракторы, концентраторы и суперконцентраторы и излагаются лучшие методы с точки зрения компромисса между случайностью, временем и пространством?...
В доказательстве разделения классов сложности по существу используется единообразие классов сложности, если доказательство не доказывает результат для неоднородной версии, например, доказательства, основанные на диагонализации (например, теоремы о пространственной и временной иерархии), существенно...
Мы много знаем об ограничениях (полиномиального размера) контуров постоянной глубины. Поскольку формулы с постоянной глубиной (полиномиального размера) представляют собой еще более ограниченную модель вычислений, все известные проблемы, которых нет в AC 0 , также не могут быть вычислены с помощью...
Какие интересные различия существуют между теорией и практикой безопасности и криптографией? Самым интересным, конечно, будут примеры, которые предлагают новые возможности для теоретических исследований, основанных на практическом опыте :). Ответы могут включать (но не ограничиваются ими): Примеры,...
Если - выпуклая функция, то неравенство Дженсена утверждает, что , и mutatis mutandis, когда вогнута. Очевидно, что в худшем случае вы не можете получить верхнюю границу в терминах для выпуклого , но есть ли граница, которая идет в этом направлении, если выпуклый, но не слишком выпуклый? Существует...
Я уже публиковал этот вопрос некоторое время назад в MathOverflow , но, насколько мне известно, он все еще открыт, поэтому я публикую его здесь в надежде, что кто-то мог о нем слышать. Постановка задачи Пусть , Q и R - три разбиения на p непустых частей (обозначаемых через P h 's, Q i ' и R j 's)...
Может ли кто-нибудь указать на один или несколько веб-сайтов, где можно загрузить работающую реализацию решателя #SAT? Меня интересуют те, кто возвращает точное количество решений, а не...
Равен ли BQP BPP с доступом к оракулу скрытой абелевой