Apakah menemukan pengurangan Logspace lebih sulit daripada pengurangan P?

Termotivasi oleh jawaban Shor terkait dengan berbagai konsep kelengkapan NP, saya mencari masalah yang NP-lengkap di bawah pengurangan P tetapi tidak diketahui NP-lengkap di bawah pengurangan Logspace (lebih disukai untuk waktu yang lama). Juga, Apakah menemukan pengurangan Logspace antara masalah NP-complete lebih sulit daripada menemukan pengurangan P?

Kaveh benar dalam mengatakan bahwa semua masalah "NP-complete" alami "mudah terlihat lengkap dalam pengurangan (seragam) . Namun, seseorang dapat membangun set yang lengkap untuk NP bawah pengurangan logspace yang tidak lengkap di bawah A C 0 pengurangan. Sebagai contoh, dalam [Agrawal et al, Computational Complexity 10 (2): 117-138 (2001)) pengkodean SAT yang mengoreksi kesalahan terbukti memiliki properti ini.$\mathrm{AC}^0$$\mathrm{AC}^0$

Mengenai kandidat "kemungkinan" untuk masalah yang selesai di bawah pengurangan waktu-poli tetapi tidak di bawah pengurangan ruang-log, seseorang dapat mencoba untuk memasak contoh formulir { : ϕ ada di SAT dan z ada di CVP [atau set lengkap-P lainnya] iff b = 1 , di mana z adalah string yang dihasilkan dengan mengambil setiap bit ke-2 ϕ }. Tentu cara naif untuk menunjukkan bahwa set ini selesai akan melibatkan komputasi pengurangan biasa untuk SAT, dan kemudian membangun z dan menghitung bit $(\phi,b)$$\phi$$z$$b=1$$z$$\phi$$z$$b$, yang secara inheren poli-waktu. Namun, dengan sedikit kerja, skema seperti ini biasanya dapat ditampilkan lengkap di bawah pengurangan ruang log melalui beberapa pengurangan non-naif. (Saya belum mengerjakan contoh khusus ini ...)