Treewith является важным параметром графа, который указывает, насколько близко граф от дерева (хотя и не в строгом топологическом смысле). Хорошо известно, что вычисление ширины дерева является NP-сложным. Существуют ли естественные классы графов, для которых сложно вычислить ширину дерева? Так же:...
В своей книге « Вычислительная сложность» Пападимитриу определяет FNP следующим образом: Предположим, что LLL является языком в NP . Согласно предложению 9.1, существует многочлен время разрешимо, полиномиальные сбалансировано соотношение RLRLR_L таких , что для всех строк xxx : Существует строку...
HT(n)HT(n)HT(n)NnnB B ( n ) = макс. HT( н )BB(n)=maxHT(n)BB(n) = \max HT(n) Что мы можем сказать о втором по величине числе в ? Назовите это .B B 2 ( n )ЧАСT( н )HT(n)HT(n)B B2( н )BB2(n)BB_2(n) B B ( n ) B B ( n ) - B B 2 ( n )B B2( н )ВВ2(N)BB_2(n) тривиально не вычислим, так как он позволяет...
Мы знаем, что проблема подсчета количества удовлетворяющих назначений в данной общей булевой формуле (CNF-SAT), заданной формуле DNF или даже заданной формуле 2SAT является проблемой # P-полной . Теперь рассмотрит CNF-SAT без отрицательного литерала (не , всегда A ). Решить задачу очень легко...
В игре с камушками на линии есть N + 1 узлы, обозначенные от 0 до N. Игра начинается с камешка на узле 0. Если на узле i есть камушек, вы можете добавить или удалить камешек из узла i + 1. Цель состоит в том, чтобы поместить гальку в узел N, не помещая одновременно много гальки на доску и не делая...
Скажем, у нас есть свойство графа, которое можно проверить в недетерминированном полиномиальном времени, и доказательство в слабой формальной системе (скажем, RCA 0 ), что свойство является минорным. Можем ли мы что-нибудь сказать о силе формальной системы, которая может доказать, что данный...
Учитывая конечный (детерминированный или недетерминированный, я не думаю, что это имеет большое значение) автомат A и порог n , принимает ли A слово, содержащее не более n различных букв? (Под k разными буквами я подразумеваю, что aabaa имеет две разные буквы, a и b .) Я показал, что эта задача...
У меня есть (надеюсь, простой, возможно, глупый) вопрос об исторической работе Бабая, показывающей, что является квазиполиномиальным.G Iграммя\mathsf{GI} Бабай показал, как получить сертификат, что два графа для i ∈ { 1 , 2 } изоморфны по времени, квазиполиномиальны по v = | V я | ,граммя= ( Vя,...
Допустим, мы хотели создать типичный, чисто функциональный язык программирования, такой как Haskell или Idris, который предназначен для системного программирования без сборки мусора и не имеет времени выполнения (или, по крайней мере, не более, чем «среды выполнения» C и Rust). То, что может...
Доказательство Омер Рейнгольда , что дает алгоритм USTCON (В U ndirected граф со специальными вершинами S и т , они Con подсоединены?) , Используя только logspace. Основная идея состоит в том, чтобы построить график расширителя из исходного графика, а затем выполнить обход в графике расширителя....
Существует старая хитрость для записи алгоритма, который, если P = NP, решает SAT за полиномиальное время. По сути, каждый перечисляет все полиномиальные машины времени и многозадачность над ними. Есть ли аналогичная уловка для односторонних функций (или даже односторонних люков)? То есть, можем ли...
В системе автоматического обучения Англуина ученик стремится выучить обычный язык L ⊆ Σ*L⊆Σ*L\subseteq \Sigma^* , задавая своему учителю два типа вопросов: Запросы по словам: если w ∈ Σ*вес∈Σ*w\in \Sigma^* , есть ли ?w ∈ Lвес∈Lw\in L Запросы на эквивалентность: если задан язык , является ли ? Если...
После прочтения недавнего вопроса «Является дополнение {www∣...}{www∣...}\{ www \mid ...\} Контекстно-свободным?» ; Я вспомнил похожую проблему, которую не смог опровергнуть: Является ли L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L = \{ ww' \mid...
Рассмотрим следующую игру на ориентированном взвешенном графе гGG с чипом в некотором узле. Все узлы гGG отмечены буквой A или B. Есть два игрока Алиса и Боб. Цель Алисы (Боба) - сдвинуть фишку к узлу, обозначенному буквой A (B). Первоначально Алиса и Боб имеют мAmAm_A и мВmBm_B долларов...
В чисто функциональном худшем случае отсортированные списки с возможностью прокрутки по постоянному времени, Brodal et al. представить чисто функциональные сбалансированные деревья с O (1) сцеплением и O (lg n) вставкой, удалением и поиском. Структура данных несколько сложна. Существует ли более...
Известно, что для обучения PAC существуют естественные классы понятий (например, подмножества списков решений), для которых существуют полиномиальные разрывы между сложностью выборки, необходимой для теоретического обучения информации неограниченным в вычислительном отношении учеником, и сложностью...
Пусть отдельные точки находятся в . Мы говорим, что точки и являются соседями, если | ij | <3 \ pmod {n-2} , что означает, что каждая точка является соседом с точками с индексами в пределах 2 , обтеканием.R 2 i j1...n1...n1 ... nR2R2\mathbb{R}^2iiijjj|i−j|<3(modn−2)|i−j|<3(modn−2)|i-j| < 3...
Какие еще языки проблем, отличные от изоморфизма графов, есть в ? Можете ли вы дать некоторые ссылки?Nп∩ c o A MNP∩coAMNP\cap coAM Обновление: Я забыл упомянуть , что я заинтересован в языках , не известно, в .c o...
Потоковые алгоритмы требуют, чтобы рандомизация по большей части выполняла какие-либо нетривиальные задачи, а из-за ограничения малого пространства нужны PRG, которые занимают мало места. Я знаю два метода, которые были процитированы для использования в потоковых алгоритмах: зависимые независимые...
Концепция секретной схемы обмена часто приписывается Шамиру (A. Shamir, Как поделиться секретом , Comm. ACM, 22 (1979), pp. 612-613.) И Blakey (GR Blakey, Защита криптографических ключей , в Proc. NCC, vol. 48, 1979, pp. 313-317.). Общая идея заключается в том, что какой-то секрет S скрыт от...