Труднее ли найти сокращения Logspace, чем сокращения P?

Воодушевленный ответом Шора, связанным с различными представлениями о NP-полноте, я ищу проблему, которая является NP-полной при сокращениях P, но неизвестно, что она является NP-полной при сокращениях Logspace (предпочтительно в течение длительного времени). Кроме того, труднее ли найти сокращения пространства журналов между NP-полными проблемами, чем найти сокращения P?

Каве прав, говоря, что все «естественные» NP-полные задачи легко увидеть как выполненные при (равномерном) сокращении . Однако можно создать наборы, которые являются полными для NP при сокращениях пространства журналов, которые не завершены при сокращениях A C 0 . Например, в [Agrawal et al., Computational Complexity 10 (2): 117-138 (2001)) было показано, что исправляющее ошибки кодирование SAT обладает этим свойством.$\mathrm{AC}^0$$\mathrm{AC}^0$

Что касается «вероятного» кандидата на проблему, которая завершается при сокращении по времени, но не при сокращении пространства журналов, можно попытаться создать пример вида { : ϕ находится в SAT, а z находится в CVP [или некоторый другой P-полный набор] тогда и только тогда, когда b = 1 , где z - строка, полученная путем взятия каждого 2-го бита ϕ }. Конечно, наивный способ показать, что этот набор завершен, будет включать вычисление обычного сокращения до SAT, а затем построение z и вычисление бита $(\phi,b)$$\phi$$z$$b=1$$z$$\phi$$z$$b$, который по своей сути поли-время. Однако, немного поработав, можно показать, что такие схемы, как правило, завершены при сокращении пространства журналов посредством некоторого не наивного сокращения. (Я не разработал этот конкретный пример ...)