Промежуточные проблемы между L и NL

26

Хорошо известно, что направленная st-связность является полной. Прорыв результат Рейнгольд показал , что неориентированный ст-связность в . Известно, что направленная st-связность находится в . Cho и Huynh определили параметризованную задачу о ранце и продемонстрировали иерархию проблем между и .NLLULcoULLNL

Я ищу больше проблем, которые являются промежуточными между и т.е. проблемы, которые:LNL

  • известно, что оно находится в но не известно (или маловероятно), что оно является полным иNLNL
  • Известно, что -Жесткий , но не известно, что в .LL
Шива Кинтали
источник

Ответы:

13

RL-полная проблема достижимости в ориентированных графах с полиномиальным временем смешивания (показанная Рейнгольдом, Тревизаном и Вадханом в псевдослучайных блужданиях на регулярных орграфах и в задаче RL vs. L ) находится в пространство (см с помощью Сакс и Zhou ), который является строго между L и Саввич Граница на NL из пространство.BPHSPACE ( S ) DSPACE ( S 3 / 2 ) O ( войти 2 п )log3/2(n)BPHSPACE(S)DSPACE(S3/2)O(log2n)

Деррик Стоули
источник
10

Полную с помощью RUL проблему достижимости в мангровых лесах можно решить в пространстве ( Allender, Lange , ). Мангровая роща - это ориентированный граф, где между любыми двумя вершинами существует не более одного пути.O(log2n/loglogn)RUSPACE(logn)DSPACE(log2n/loglogn)

Деррик Стоули
источник
1
См. Также: Ланге, «Однозначный класс, обладающий полным набором» STACS '97.
Деррик Столи
6

Известно, что идеальное совпадение находится в (но не в ). Поскольку планарная достижимость сводится к этому, он является -hard.U Lc o U L LULULcoULL

Ссылка: Самир Датта, Рагхав Кулкарни, Рагхунат Тевари: Идеальное соответствие в двудольных плоских графах в UL. Электронный коллоквиум по вычислительной сложности (ECCC) 17: 201 (2010)

SamiD
источник
Я думаю, что я должен быть немного смущен из-за устаревшего ответа - но только ради полноты.
SamiD