Существуют ли NP-полные (или даже NP-сложные, или NP) задачи, которые имеют хорошие топологические свойства для изучения. Есть ли у задач NP теоретические формулировки узлов? Мы знаем о результатах # о полиноме Джонса. Графические задачи (вложения?), В частности раскраски графов, могут иметь...
Я совершенно уверен, что я не первый, кто принимает идею, которую я собираюсь представить. Однако было бы полезно, если бы я мог найти какую-либо литературу, связанную с этой идеей. Идея состоит в том, чтобы построить машину Тьюринга M со свойством, что если P = NP, то M будет решать 3-SAT за...
Как можно показать, что определенное свойство не может быть выражено в 2-CNF (2-SAT)? Существуют ли игры, такие как игры в гальку? Похоже, что классическая игра с черной галькой и игра с черной и белой галькой для этого не подходят (они завершены PSPACE, согласно Hertel и Pitassi, SIAM J of...
Пусть - булева функция с чувствительностью s ( f ) и чувствительностью блока b s ( f ) .еffs ( f)s(f)s(f)b s ( f)bs(f)bs(f) Гипотеза о чувствительности блока чувствительности утверждает, что существует такое , что ∀ f , b s ( f ) ≤ s ( f ) c .с > 0c>0c>0∀ ф, b s ( f ) ≤ s (...
Пусть будет константой. Как мы можем с уверенностью построить псевдослучайный генератор, который обманывает конечные автоматы d- состояния?dddddd Здесь, -state имеет конечные автоматы d узлов, начальный узел, набор узлов , представляющие принимают состояния, и две направленных ребер помечены 0, 1 ,...
Я не теоретик информатик. Я стабильный теоретик гомотопий, использующий -категории. Я видел применения теории категорий и теории топосов к теоретической информатике, и мне было интересно, можно ли каким-либо образом использовать -категории (и, предпочтительно, для меня, теория стабильной гомотопии)...
Существуют ли примеры практического применения паритетных игр, то есть систем, в реальном мире, которые можно представить как паритетные игры? Обычно связанная документация по паритетным играм практически никогда не имеет практического примера этого...
Я пытался обернуть голову вокруг того, что, почему и как вычислить, но я не могу понять, «почему это работает»?λλ\lambda «Интуитивно» я получаю модель вычислимости машин Тьюринга (ТМ). Но эта абстракция просто оставляет меня в замешательстве.λλ\lambda Давайте предположим, что ТМ не существуют -...
В статье «О сложности некоторых раскрасок» Бодлендер дает несколько открытых вопросов о сложности решения, имеет ли игрок 1 или 2 выигрышную стратегию в некоторых играх раскраски графов. Кто-нибудь знает, были ли они решены? 1) В одной игре два игрока по очереди выбирают одну вершину на графике и...
Естественный барьер доказательств Разборова и Рудича утверждает, что при достоверных криптографических предположениях нельзя надеяться отделить NP от P / poly, найдя комбинаторные свойства функций, которые являются конструктивными, большими и полезными. Есть несколько хорошо известных результатов,...
Существуют ли алгоритмы переупорядочения данных для оптимизации для сжатия? Я понимаю, что это специфично для данных и алгоритма сжатия, но есть ли слово для этой темы? Где я могу найти исследования в этой области? В частности, у меня есть список json с 1,5 миллионами строк, и я хочу изменить...
Какие проблемы со следующими свойствами: 1) они являются ограничением (возможно общеизвестных) проблем, которые являются PSPACE-полными; 2) ограниченные версии находятся в PSPACE, но это открытая проблема, если они завершены PSPACE (или даже если они NP-hard). Четыре примера из "головоломки и С.":...
Я читаю обзоры Тревизана и Ловетта о применении аддитивного комбинаторика в TCS. Большинство этих приложений подпадают под сложность вычислений , например, нижние границы. Интересно, нашла ли аддитивная комбинаторика применение в разработке алгоритмов ? Мотивация для моего вопроса заключается в...
Подумайте о модели клеточного зонда. Существует ли структура данных, которая может выделять непрерывные порции памяти любой длины (например, malloc в C) и освобождать их, избегая при этом сегментации памяти, и выполняет каждую операцию в наихудший случай детерминированного времени O (log n), где n...
Я ищу список об известной или неизвестной сложности различных теоретико-алгебраических задач. Например, GCD в открыт,NC1NC1NC^1 факторинг в открыт,PPP вычисление когомологий пучка -hard#P#P\#P , Арора и Барак утверждают, что вариант факторинга является -полным (хотя это не ясно из обсуждения в...
Известно, что добавление рандомизации с ограниченной ошибкой в PSPACE не добавляет мощности. То есть BPPSAPCE = PSPACE. Известно, что P = BPP известно, но известно, что .Б Пп⊆ Е2∩ Π2Впп⊆Σ2∩Π2BPP\subseteq \Sigma_2\cap \Pi_2 Таким образом, возможно (хотя предполагается, что оно ложно), что...
Каковы некоторые (не очень известные) утверждения о том, что, если это правда, PH должен разрушиться? Ответы, содержащие краткое высокоуровневое утверждение со ссылками, приветствуются. Я попытался выполнить обратный поиск без особой...
Пусть kkk фиксировано, и пусть GGG (связный) граф. Если я не ошибаюсь, из работы Бодлендера [1, теорема 3.11] следует, что если ширина дерева GGG примерно равна 2k32k32k^3 , то GGG содержит звезду K1,kK1,kK_{1,k} в качестве минора. Можем ли мы сделать срок 2k32k32k^3 меньше? То есть, говорит ли...
P/poly=NP/polyP/poly=NP/polyP/poly = NP/poly означает , что, в свою очередь, имеет интересные последствия, такие как коллапс полиномиальной иерархии.NP⊆P/polyNP⊆P/polyNP \subseteq P/poly Есть ли интересные последствия для ?P/poly≠NP/polyP/poly≠NP/polyP/poly \neq...
Для данного графа нам нужно найти мощность наибольшего множества вершин, чтобы каждая из них присутствовала в каждом максимально возможном сопоставлении.граммGG Есть ли решение помимо очевидного удаления каждой вершины и найти максимальное совпадение, чтобы увидеть, как оно...