Является ли следующее решение задачи NP-завершенным: Пусть неориентированный граф и двумя целыми числами. Можно ли выбрать для каждой вершины ровно разных соседей, чтобы ни один узел не был выбран больше, чем раз.GGGb≤cb≤cb \le cGGGbbbccc Случай может быть решен для любого за полиномиальное время с...
Позволять ВVV быть набором DDDпрямоугольные формы. Заd∈ { 1 , . , , , D }d∈{1,...,D}d \in \{1,...,D\} а также v ∈ Vv∈Vv \in V, wd(v)∈Q+wd(v)∈Q+w_d(v) \in \mathbb{Q}^{+} описывает длину vvv в измерении ddd, То же обозначение используется для контейнераCCC, DDDзадача об ортогональной упаковке...
Этот пост отделен от Последствия UP равно NP , а также является дополнительным вопросом к классам семантической и синтаксической сложности . В вышеприведенном посте мы узнали о семантических и синтаксических классах. Вкратце, если класс можно охарактеризовать как листовой класс языка , то класс...
Как вы все знаете, из-за финансового кризиса 2008 года продолжаются последствия. Я думал о том, как теория сложности вписывается во все это, когда я понял, что не знаю базовых классов сложности, связанных с финансовой экономикой. Поэтому мой вопрос заключается в том, какова классификация сложности...
В сложности дерева решений для булевой функции очень хорошо известный метод нижней границы состоит в том, чтобы найти (приблизительный) многочлен, который представляет функцию. Патури дал характеристику для симметричных булевых (частичных и полных) функций в терминах величины, обозначаемой...
Этот вопрос возник в контексте криптографии, но ниже я представлю его с точки зрения теории сложности, поскольку здесь люди больше знакомы с последним. Этот вопрос связан с проблемами в NP, но не в Average-P / poly и неоднородности биения по Oracle Access . Неформальное утверждение: когда...
Мне повлиял необычайный взрыв в сглаженном анализе, и меня поразило утверждение в статье « Сглаженный анализ целочисленного программирования» . Это говорит о том, что целочисленное линейное программирование находится в сглаженном P, если оно ограничено полиномами. Это было существенно верно в силу...
Определите, что вычислительная модель MPostBQP идентична PostBQP, за исключением того, что мы разрешаем полиномиально много измерений в кубитах перед последующим выбором и окончательным измерением. Можем ли мы привести какие-либо доказательства того, что MPostBQP более мощный, чем PostBQP?...
Похоже, что в популярных языках запросов для реляционных баз данных можно создавать запросы, для ответа на которые потребуется много ресурсов. На практике администраторы базы данных управляют этим, ограничивая объем памяти на запрос и проверяя наличие длительных запросов на предмет замедления в...
Даже если это не решающий момент, я не вижу литературы по этому вопросу. Есть ли результаты релятивизации? Разве не было бы достаточно просто доказать строгое включение путем адаптации недетерминированной теоремы иерархии времени, исследуя все возможные пути машины...
Пусть будет матрица или с элементами . Может ли кто-нибудь предоставить мне матрицу чтобы ? Что такое наименьший явный B, который известен таким образом, что \ operatorname {per} (A) = \ det (B) ? Любые ссылки на это с явными примерами?AAA3 × 33×33 \times 34 × 44×44 \times 4aя жaija_{ij}ВBBв( A ) =...
Я хотел бы ограничить мощность множества графов единичных дисков с NNNВершины. Известно, что проверка того, является ли граф членом этого набора, является NP-сложной задачей. Приводит ли это к какой-либо нижней границе мощности, предполагая, что P≠≠\neq NP? Например, предположим, что есть порядок...
Колмогоровская сложность строки не вычислима. Тем не менее, в случайном подмножестве размераMMM двоичных строк длины nNnсколько ожидается, что сложность будет меньше целого числа n0N0n_{0} меньше, чем nNn (как функция MMM, nNn а также...
Везде, где я читаю о проблеме разреженного разреза, это говорит только о том, что проблема, как известно, является NP- трудной. Где я могу найти подтверждение этому? Какая известная NP- трудная проблема сводится к проблеме разреженного разреза? Я не смог найти никаких доказательств в книге Вазирани...
Я пытаюсь показать, что определенная проблема недопустима из-за сокращения охвата. Мое сокращение превращает экземпляр с базовым набором размера и устанавливает в экземпляр моей проблемы, где определенный параметр имеет размер . Затем я могу показать, что экземпляр установленного покрытия, где...
В задаче Макс-Кута ищется подмножество S вершин данного простого неориентированного графа так, чтобы число ребер между S и дополнением к S было как можно большим. Max-Cut является APX-полным на графах с ограниченной степенью [PY91] и фактически APX-полным на кубических графах (т.е. графах степени...
DLOGTIME определяется по адресу http://en.wikipedia.org/wiki/DLOGTIME определяется по адресу http://en.wikipedia.org/wiki/L_%28complexity%29 и определены по адресу http://en.wikipedia.org/wiki/NC_%28complexity%29 LL\operatorname{L} Северная КаролинаNC\operatorname{NC}Северная...
Предположим структуру в сложности коммуникации, где у нас есть два игрока A (вши) и B (ob) и R (eferee). А и Б не общаются напрямую друг с другом. В каждом раунде общения каждый из них отправляет сообщение (mAmAm_A, mBmBm_B) в R.R вычисляет две функции fA(mA,mB)fA(mA,mB)f_A(m_A,m_B) а также...
В предыдущем вопросе « Параметризованный алгоритм поиска бикликов» я поинтересовался, существуют ли быстрые параметризованные алгоритмы для нахождения -биклика в графе вершин, и узнал, что он открыт, если он равен FPT относительно . То же самое верно и для подсчета в -bicliques, или известно , что...
Есть некоторые проблемы NP-Complete ( , \ mathsf {SUBSETSUM} и т. Д.), О которых известно, что они находятся в \ mathsf {DSPACE (n)} . Как насчет сублинейных пространств?SATSAT \mathsf{SAT} SUBSETSUMSUBSETSUM \mathsf{SUBSETSUM} DSPACE(n)DSPACE(n) \mathsf{DSPACE(n)} Существует ли какая-либо...