Проблемы с большими открытыми пробелами в сложности

32

Этот вопрос касается проблем, для которых существует большой открытый разрыв сложности между известной нижней границей и верхней границей, но не из-за открытых проблем самих классов сложности.

Чтобы быть более точным, скажем, у проблемы есть классы промежутков A,B (с , не определенным однозначно), если - максимальный класс, для которого мы можем доказать, что это жесткий, а - минимальный известный верхний связаны, т.е. у нас есть алгоритм в решающий задачу. Это означает, что если мы в конечном итоге обнаружим, что задача полна с , это не повлияет на теорию сложности в целом, в отличие от поиска алгоритма для полной задачи.A A B B C A C B P N PABAABBCACBPNP

Меня не интересуют проблемы с и , потому что это уже объект этого вопроса .B = N PAPB=NP

Я ищу примеры проблем с гэп-классами, которые максимально возможны. Чтобы ограничить сферу и уточнить вопрос, меня особенно интересуют проблемы с и , означающие, что как членство в и -полнота согласованы с текущими знаниями, без разрушения известных классов (скажем, классов из этот список ).B E X P T I M E P E X P T I M EAPBEXPTIMEPEXPTIME

Денис
источник
Что вы подразумеваете под классами проблемы? Предположим, что проблема в SAT, как вы определяете классы?
РБ
SAT является NP-полной, поэтому мы можем взять и здесь нет пробела, потому что сложность SAT точно соответствует уже известному классу. Показ любого нового результата о сложности SAT (а именно, принадлежность к меньшему классу) был бы прорывом в теории сложности. Конечно, вопрос не является полностью четко определенным, поскольку он зависит от того, какие классы сложности считаются «основными», а A , B не определяются однозначно. Тем не менее, конкретный вопрос четко определен: примеры языков, для которых он согласуется с текущими знаниями о том, что они написаны на P или EXPTIME. A=B=NPA,B
Денис
на самом деле все еще не вполне четко определены из-за «неразрушающегося», поэтому он опирается на понятие «хорошо известного класса». Очевидно, что PSPACE-полная задача не соответствует требованию, хотя нахождение в P или EXPTIME-завершении согласуется с современными знаниями. Например, этот список можно использовать в качестве ссылки для того, что является «известным» классом: en.wikipedia.org/wiki/List_of_complexity_classes
Денис
13
Это не совсем подходит счет вашего конкретного вопроса , но судя по всему , экзистенциальная теория чисел упорно сопротивляется любой дальнейшей классификации сверх быть NP-трудной и в PSPACE (последняя в 1988 результате JF Осторожные). en.wikipedia.org/wiki/Existential_theory_of_the_reals
анемон

Ответы:

28

Узел Эквивалентность задачи .

Учитывая, что на плоскости нарисованы два узла, они топологически одинаковы? Эта проблема, как известно, разрешима, и, как представляется, нет никаких препятствий вычислительной сложности, связанных с ее нахождением в P. Лучшая верхняя граница, известная в настоящее время по своей временной сложности, представляется башней из s высоты c n , где c = 10 10 6 , а n - количество пересечений на диаграммах узлов. Это связано с тем, что Ковард и Лакенби ограничивают количество ходов Рейдемейстера, необходимое для перехода одного узла к эквивалентному. Смотрите более свежую статью Лакенби2cnc=10106n для некоторых более недавних связанных результатов и для явной формы оценки, которую я даю выше (страница 16).

Питер Шор
источник
Спасибо за ваш ответ. Вы знаете текущие границы? Можете ли вы указать ссылку на текущее состояние техники? У меня проблемы с поиском ясного.
Денис
Я пытался пойти найти что - то более современное , чем в 1998 году бумаги Хасс, Lagarias и Pippenger здесь . Это говорит о том, что проблема эквивалентности узлов, как известно, разрешима. Я не был бы удивлен, если бы кто-то показал, что это было в EXPTIME с тех пор, но я не верю ничему лучше, чем это известно, и, конечно, не ясно, что это не в P. Я совершенно уверен, что никто из результатов, показывающих, что решение, является ли что-то завязанным в NP, распространяется на эту более общую проблему.
Питер Шор
Этот вопрос МО связан с: mathoverflow.net/questions/77786/… В частности, используя последние результаты, объявленные Лакенби в people.maths.ox.ac.uk/lackenby/ekt11214.pdf , можно получить их для любого узла типа K, определение того, является ли данный узел эквивалентным K, находится в NP (обратите внимание, что это не улучшает проблему эквивалентности узлов)
Арно
@Arnaud: на самом деле, мне кажется, что эти результаты доказывают, что для двух диаграмм с не более чем n пересечений, Проблема Эквивалентности Узлов может быть решена за время максимум двух башен высотой , где c - огромная постоянная , Я должен проверить это и отредактировать свой ответ. cnc
Питер Шор
@PeterShor Да, действительно. Я сосредоточился на более недавнем результате, потому что он может привести к улучшенной границе, когда он публикуется, если эксплицирован фактический полином.
Арно,
23

Вот версия проблемы размера минимальной схемы (MCSP): учитывая бит Таблица истинности булевой функции, у него есть цепь размера не более 2 л / 2 ?2n2n/2

Известно, что не в . Содержится в N P . Обычно считается, что N P -hard, но это открыто. Я считаю, что это даже не известно, что A C 0 [ 2 ] -hard. Действительно, недавняя работа с Коди Мюрреем (которая появится в CCC'15) показывает, что нет единого снижения NC0 с PARITY до MCSP.AC0NPNPAC0[2]

Райан Уильямс
источник
23

Сложность вычисления бита (заданного в двоичном виде) иррационального алгебраического числа (такого как ) имеет наилучшую известную верхнюю границу P P P P P P P посредством редукции к задаче B i t S L P, которая, как известно, имеет эту верхнюю границу[ABD14]. С другой стороны, мы даже не знаем, сложнее ли эта проблема, чем вычисление четностиnбитов - для всех мы знаем, что эта проблема может быть вA C 0 . Заметим, однако, что мы знаем, что никакой конечный автомат не может вычислить биты иррационального алгебраического числа[AB07]2PPPPPPPBitSLPnAC0

SamiD
источник
21

Другой естественной топологической проблемой, сходной по духу с ответом Питера Шора, является вложимость двумерных абстрактных симплициальных комплексов в R3 . В общем - то естественно спросить , когда мы можем эффективно / эффективно решить , что абстрактный - мерный симплициальный комплексk может быть встроен в . Для k = 1 и d = 2 это проблема плоскостности графа и имеет алгоритм линейного времени. Для k = 2 и d = 2 также существует линейный алгоритм времени . Rdk=1d=2k=2d=2 , d = 3 дело было открыто до прошлого года, когда былодоказано, что оно решаемо Матусеком, Седжвиком, Тансером и Вагнером. Они говорят, что их алгоритм имеетпримитивную рекурсивнуювременную привязку, нобольшую, чем башня экспонент. С другой стороны, они предполагают, что, возможно, можно поставить проблему в NP, но выход за пределы этого будет проблематичным. Тем не менее, нет никаких убедительных доказательств того, что алгоритм polytime невозможен.k=2d=3

Последняя статья имеет много ссылок для дальнейшего чтения.

Сашо Николов
источник
16

Многочисленные автоматы (MCA) - это конечные автоматы, оснащенные счетчиками, которые можно увеличивать и уменьшать за один шаг, но в качестве чисел принимают только целые числа> = 0. В отличие от машин Мински (иначе называемых автоматами счетчиков), MCA не разрешается проверять, равен ли счетчик нулю.

Одной из алгоритмических проблем с огромным разрывом, связанным с MSC, является проблема достижимости. Например, может ли автомат достигнуть из конфигурации с начальным состоянием и всеми счетчиками нуля, конфигурации с принимающим состоянием и всеми счетчиками снова с нуля.

Проблема сложна для EXPTIME (как показано Ричардом Липтоном в 1976 г.), разрешима (Ernst Mayr, 1981) и разрешима в Fω3 (спасибо, Сильвен, за указание на это). Огромный разрыв.

Томас С
источник
3
Hi Thomas, there is a claim of an explicit (and most likely not tight) complexity upper bound in a recent arXiv paper: arxiv.org/abs/1503.00745. The proposed upper bound in Fω3 is however way beyond the complexity classes the original poster was interested in.
Sylvain
@Sylvain Cool! Thanks for sharing this. :)
Michael Wehar
@Sylvain Is EXPTIME the best known lower bound?
Michael Wehar
2
Fω
@Sylvain Большое спасибо за всю дополнительную информацию. Я очень ценю это. :)
Майкл Вехар
11

QMA(2) (Quantum Merlin-Arthur with two unentangled provers): certainly QMA-hard, but only known to be in NEXP.

Martin Schwarz
источник
9

The computational problem associated to Noether's Normalization Lemma for explicit varieties ("explicit" in the sense of this paper [freely available full version]). Best known upper bound is EXPSPACE (note, SPACE, not TIME!) but it is conjectured to be in P (and indeed, its being in P is essentially equivalent to derandomizing PIT).

Joshua Grochow
источник
Can you provide more info on this in an explicit form? looks like some kind of bpp-complete problem?
@Arul: Neither PIT nor this problem is BPP-complete in any sense that I am aware of. (In fact, showing that BPP-complete problems exist is still open, and requires non-relativizing techniques - a result going back to Sipser.) However, derandomizing either has a hardness-randomness trade-off, in that their derandomization is essentially equivalent to lower bounds. Aside from the paper linked in the answer ("GCT 5"), lookup hardness-randomness and Kabanets-Impagliazzo.
Joshua Grochow
I will do that but I was interested in this phrase 'and indeed, its being in P is essentially equivalent to derandomizing PIT' which seems to say PIT is some kind of proxy complete problem
@Arul: Yes, to see why PIT is such a "proxy complete problem," see the things I referred to in my previous comment.
Joshua Grochow
why does he use 'Dedicated to Sri Ramakrishna' in many of his works?
6

The Skolem problem (given a linear recurrence with integer base cases and integer coefficients, does it ever reach the value 0) is known to be NP-hard and not known to be decidable. As far as I know anything in between would be consistent with our current knowledge without any collapses of standard complexity classes.

David Eppstein
источник