Хорошо известно, что направленная st-связность является полной. Прорыв результат Рейнгольд показал , что неориентированный ст-связность в . Известно, что направленная st-связность находится в . Cho и Huynh определили параметризованную задачу о ранце и продемонстрировали иерархию проблем между и .
Я ищу больше проблем, которые являются промежуточными между и т.е. проблемы, которые:
- известно, что оно находится в но не известно (или маловероятно), что оно является полным и
- Известно, что -Жесткий , но не известно, что в .
источник
Известно, что идеальное совпадение находится в (но не в ). Поскольку планарная достижимость сводится к этому, он является -hard.U L ∩ c o U L LUL UL∩coUL L
Ссылка: Самир Датта, Рагхав Кулкарни, Рагхунат Тевари: Идеальное соответствие в двудольных плоских графах в UL. Электронный коллоквиум по вычислительной сложности (ECCC) 17: 201 (2010)
источник