Вопросы с тегом «polynomial-time»

55
Почему 2SAT в P?

Я сталкивался с полиномиальным алгоритмом, который решает 2SAT. Мне показалось удивительным, что 2SAT находится в P, где все (или многие другие) экземпляры SAT являются NP-Complete. Что отличает эту проблему? Что делает его таким простым (NL-Complete - даже проще, чем...

31
Какие классы математических программ могут быть решены точно или приблизительно за полиномиальное время?

Меня довольно смущает литература по непрерывной оптимизации и литература TCS о том, какие типы (непрерывных) математических программ (МП) могут быть эффективно решены, а какие нет. Сообщество непрерывной оптимизации, кажется, утверждает, что все выпуклые программы могут быть решены эффективно, но я...

30
Существует ли алгоритм полиномиального времени, чтобы определить, содержит ли диапазон набора матриц матрицу перестановок?

Я хотел бы найти алгоритм полиномиального времени, который определяет, содержит ли диапазон данного набора матриц матрицу перестановок. Если кто-нибудь знает, относится ли эта проблема к другому классу сложности, это было бы так же полезно. РЕДАКТИРОВАТЬ: я пометил этот вопрос с помощью линейного...

25
Нахождение простого больше заданной границы

Является ли детерминированный алгоритм за полиномиальное время известным для следующей задачи: Ввод: натуральное число (в двоичной кодировке)Nnn Выход: простое число .р > нp>np > n (Согласно списку открытых проблем Леонарда Адлемана, проблема была открыта в 1995 году.)...

23
Для какого k PLANAR NAE k-SAT в P?

Задача «Не все равно kkk -SAT» (NAE kkk -SAT), учитывая набор CCC предложений над набором XXX булевых переменных, так что каждое предложение содержит не более kkk литералов, спрашивает, существует ли истинное присвоение переменных таким образом, чтобы каждое предложение содержит, по крайней мере,...

21
Как быстро мы можем решить полностью унимодулярную целочисленную линейную программу?

(Это продолжение этого вопроса и его ответа .) У меня есть следующая полностью унимодулярная (TU) целочисленная линейная программа (ILP). Здесь - все натуральные числа, заданные как часть входных данных. Указанное подмножество переменных x i j устанавливается в ноль, а остальные могут принимать...

21
Есть ли естественная проблема в квазиполиномиальном времени, но не в полиномиальном времени?

Ласло Бабаи недавно доказал, что проблема изоморфизма графа находится в квазиполиномиальном времени . См. Также его выступление в Чикагском университете, заметки о выступлениях Джереми Куна GLL, пост 1 , GLL, пост 2 , GLL, пост 3 . Согласно теореме Ладнера, если , то не является пустым, т. содержит...

21
Может ли

Рассмотрим язык E Q UA L I T Y ={ аNбN∣ n ≥ 0 }ЕQUALяTYзнак равно{aNбN|N≥0} \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} . Известно, что E Q UA L I T YЕQUALяTY \mathtt{EQUALITY} не может быть распознано ни одной чередующейся машиной Тьюринга (АТМ) с сублогарифмическим пространством (Szepietowski,...

18
Какие известные модели автоматов имеют полиномиально разрешимую локализацию?

Я пытаюсь решить конкретную проблему, и я подумал, что смогу решить ее, используя теорию автоматов. Мне интересно, какие модели автоматов имеют разрешимость за полиномиальное время? то есть если у вас есть машины вы можете проверить, эффективно ли . L ( M 1 ) ⊆ L ( M 2 )M1, M2M1,M2M_1, M_2Л ( М1) ⊆...

15
Имея 4-циклический свободный граф

Проблема цикла заключается в следующем:Кkk Экземпляр: неориентированный граф с n вершинами и до ( nграммGGNnn края.( н2)(n2)n \choose 2 Вопрос: существует ли (правильный) цикл в G ?КkkграммGG Предыстория: для любого фиксированного мы можем решить цикл за времени.2 k O ( n 2 )Кkk2 к2k2kO (...

14
Является ли eta-эквивалентность для функций совместимой с операцией seke в Haskell?

Лемма: Предполагая, что эта эквивалентность у нас есть (\x -> ⊥) = ⊥ :: A -> B. Доказательство: ⊥ = (\x -> ⊥ x)по eta-эквивалентности и (\x -> ⊥ x) = (\x -> ⊥)по сокращению под лямбду. В отчете Haskell 2010, раздел 6.2, seqфункция определяется двумя уравнениями: seq :: a -> b...

14
Содержит ли P языки, существование которых не зависит от PA или ZFC? (Сообщество TCS вики)

Ответ: не известно. Задаваемые вопросы являются естественными, открытыми и, по-видимому, сложными; сейчас вопрос вики сообщества. обзор Вопрос состоит в том, чтобы разделить языки, принадлежащие к классу сложности PPP  - вместе с машинами Тьюринга (TM), которые принимают эти языки, - на два...

14
Каковы последствия

Язык находится в если существует машина Тьюринга для пространства журналов, которая решает язык с полиномиальным количеством рекомендаций.Л / р о л уL/поLYL/poly Смотрите здесь для получения дополнительной информации: https://en.wikipedia.org/wiki/L/poly Вопрос Каковы последствия ?п⊆L / p o l...

13
Примеры проблем, когда экспоненциальные алгоритмы работают быстрее, чем полиномиальные алгоритмы для практических размеров?

Знаете ли вы о каких-либо проблемах (предпочтительно, по крайней мере, несколько хорошо известных), где для практического размера задачи экспоненциальный алгоритм работает намного быстрее, чем самый известный аналог полиномиального времени. Например, предположим, что задача имеет практический...

13
Каково эквивалентное определение mP / poly в терминах машины Тьюринга?

P / poly - это класс задач решения, решаемых семейством булевых схем полиномиального размера. В качестве альтернативы его можно определить как машину Тьюринга за полиномиальное время, которая получает строку подсказки, которая имеет полиномиальный размер по n и основана исключительно на размере n....

13
Какие целочисленные линейные программы просты?

Пытаясь решить проблему, я выразил ее часть в виде следующей целочисленной линейной программы. Здесь - все натуральные числа, заданные как часть входных данных. Указанное подмножество переменных x i j устанавливается в ноль, а остальные могут принимать положительные целые...

13
Существуют ли интересные графовые классы, в которых сложно вычислить ширину дерева?

Treewith является важным параметром графа, который указывает, насколько близко граф от дерева (хотя и не в строгом топологическом смысле). Хорошо известно, что вычисление ширины дерева является NP-сложным. Существуют ли естественные классы графов, для которых сложно вычислить ширину дерева? Так же:...

13
Подсчет количества удовлетворяющих заданий в ПОЗИТИВНОМ CNF-SAT

Мы знаем, что проблема подсчета количества удовлетворяющих назначений в данной общей булевой формуле (CNF-SAT), заданной формуле DNF или даже заданной формуле 2SAT является проблемой # P-полной . Теперь рассмотрит CNF-SAT без отрицательного литерала (не , всегда A ). Решить задачу очень легко...

12
NP-твердость частного случая нумерации

Рассмотрим следующую проблему: Учитывая набор из положительных чисел { a 1 , … , a n }, в которых k ≥ 3 является константой, мы хотим разбить набор на m подмножеств размера k так, чтобы произведение суммы каждого подмножества максимальноn=kmn=kmn = k m{a1,…,an}{a1,…,an}\{ a_1, \dots, a_n \}k≥3k≥3k...