Есть ли понятие вычислимости на множествах, отличных от натуральных чисел? Ради аргумента, скажем , на множествах SSS , что biject с NN\mathbb{N} . Соблазнительно сказать «да, это те функции вида g∘f∘g−1g∘f∘g−1g \circ f \circ g^{-1} где ggg - любая биекция N→SN→S\mathbb{N} \to S а fff - любая...
Теорема Махейни говорит нам , что если есть разреженная -полное множество под полиномиальное время многие-одно сокращение, то P = N P . (См. « Разреженные комплекты для NP: Решение гипотезы Бермана и Хартманиса »)NпNPNPP=NPP=NPP = NP Известны ли последствия существования разреженных полных наборов...
Я наткнулся на два примера гипотетической сложности некоторых графовых задач. Гипотетическая твердость означает, что опровержение некоторой гипотезы подразумевает NP-полноту соответствующей задачи графа. Например, гипотеза Барнетта утверждает, что каждый 3-связный кубический плоский двудольный граф...
Пусть будет полиномиальный детерминированный машина , которая может задавать вопросы некоторым оракулом А . Первоначально A пусто, но это можно изменить после игры, которая будет описана ниже. Позвольте x быть некоторой строкой.MMMAAAAAAxxx Рассмотрим следующую игру Алисы и Боба. Первоначально...
Что вы думаете о регулярном чтении газет вне своей области, даже тех, которые не связаны с его областью? Моя интуиция заключается в том, что это может дать совершенно иную перспективу или технику, которая может помочь мне в моих собственных проблемах. Но в то же время я немного скептически отношусь...
Существует ли алгоритм сортировки, основанный на сравнении, который использует среднее из сравнений ?l g (n!)+o(n)lg(n!)+o(n)\mathrm{lg}(n!)+o(n) Существование алгоритма сравнения в худшем случае является открытой проблемой, но среднего случая достаточно для рандомизированного алгоритма с...
Существуют ли примеры случаев, когда классическое моделирование квантового алгоритма для задачи превосходит лучший ранее известный классический алгоритм для этой задачи? «Превосходит» не обязательно означает другой класс сложности, это может быть просто лучшее масштабирование. Этот вопрос был...
Я нахожусь в ситуации, когда мне нужно показать, что проверка типов решаема для исчисления с зависимым типом, над которым я работаю. До сих пор я был в состоянии доказать, что система сильно нормализуется, и, таким образом, равенство определений разрешимо. Во многих ссылках, которые я читал,...
В настоящее время я ищу предмет для диссертации и столкнулся с областью алгоритмической теории информации. Поле кажется мне очень интересным, но, кажется, все поле было сделано за много лет. Итак, мой вопрос: поле «живое» или оно в значительной степени закрыто? Есть ли у него открытые вопросы?...
Класс NCiNCi\textrm{NC}^i является классом функций, вычисляемых семействами схем ограниченного вкручивания, размера nO(1)nO(1)n^{O(1)} и глубины O(logi(n))O(logi(n))O(\log^i(n)) . NCNC\textrm{NC} -hierarchy является объединением этих классов. Есть ли какое-либо исследование линейного размера этой...
Это обобщение моего предыдущего вопроса . Пусть будет полиномиальный детерминированный машина , которая может задавать вопросы некоторым оракулом . Первоначально пусто, но это можно изменить после игры, которая будет описана ниже. Позвольте x быть некоторой строкой.MMMAAAAAAxИксx Рассмотрим...
С начала 70-х годов известно, что и не равны (потому что не является замкнутым в полиномиальном времени многих одно сокращение, в отличие от ). Однако, насколько мне известно, до сих пор не ясно, является ли один класс подмножеством другого, или они несопоставимы, то есть и оба непусты.NPNP{\bf...
В зоопарке сложности говорится [ 1 ], что в описательной сложности может быть определен тремя различными типами формул: который также является , а также как .ппPFO ( L Fп)FО(LFп)FO(LFP)FO ( nO ( 1 ))FО(NО(1))FO(n^{O(1)})SO ( HO R N)SО(ЧАСОрN)SO(HORN) Однако есть некоторые исключения, например, не...
Мне интересно, может ли кто-нибудь подсказать мне, почему строгая положительность индуктивных типов данных гарантирует строгую нормализацию. Чтобы было ясно, я вижу, как наличие отрицательных явлений приводит к расхождению, то есть путем определения: data X where Intro : (X->X) -> X мы можем...
Я давно интересовался различными темами, такими как комбинаторная логика, лямбда-исчисление, функциональное программирование, и изучал их. Однако, в отличие от «Теории вычислений», которая стремится ответить на вопрос «вычислимости», то есть вещей, которые могут / не могут быть вычислены с...
Мы знаем, что в мы не можем решить SUM за время при любой функции (обычно ).ЕTЧАСЕTЧАСETHККKе( К) Р о л у( п К)е(К)поLY(NК)f(K)poly(nK)е( К)е(К)f(K)2О ( К)2О(К)2^{O(K)} Существует ли какая-либо гипотеза, которая предотвращает сложность (это полностью согласуется с возможностью, так как нам нужно...
Задача двухцветного идеального сопоставления состоит в том, чтобы решить, имеет ли граф раскраску с двумя цветами, чтобы у каждого узла был ровно один сосед того же цвета, что и он сам. Шефер доказал, что задача является NP-полной . Он остается NP-полным даже для плоских кубических графов. Меня...
Учитывая граф G1, G2 и G3, мы хотим выполнить тест F изоморфизма между G1 и G2, а также G1 и G3. Если G2 и G3 очень похожи, так что G3 формируется путем удаления одного узла и вставки одного узла из G2, и у нас есть результат F (G1, G2), можем ли мы вычислить F (G1, G3), не вычисляя его с нуля...
Робин Ганди был учеником Алана Тьюринга . Ганди сделал анализ Аналитического двигателя Бэббиджа (см. «Ганди - Слияние идей в 1936 году», цитируемый в «Херкен, Рольф - Универсальная машина Тьюринга - Обследование за полвека . Springer Verlag») - и сказал, что это сделал (ср. стр. 52–53):...
Рассмотрим связный неориентированный граф с неотрицательными весами ребер и двумя выделенными вершинами s,ts,ts,t . Ниже приведены некоторые задачи на пути, которые имеют следующую форму: найдите путь s−ts−ts-t , чтобы некоторая функция весов ребер на пути была минимальной. В этом смысле все они...