Теорема Махейни говорит нам , что если есть разреженная -полное множество под полиномиальное время многие-одно сокращение, то P = N P . (См. « Разреженные комплекты для NP: Решение гипотезы Бермана и Хартманиса »)
Известны ли последствия существования разреженных полных наборов для других классов сложности? В частности, если существует редкое неполное множество при сокращениях пространства журнала «один-один», означает ли это P = L ?
Да, именно то , что вы предложили верно: если есть разреженная -полное множество под лог-пространстве многих-одно сокращение, то P = L . Это было предположено Хартманисом в 1978 году и доказано Цаем и Сивакумаром в 1995 году. См. Эту статью .
Хартманис также высказано предположение , что если имеется разреженная -полным множество под лог-космических многих-один сокращений, а затем N L = L . Это также было доказано Цаем и Сивакумаром в 1997 году; см. этот другой документ .