Pada set lengkap yang jarang dan P vs L

Teorema Mahaney memberi tahu kita bahwa jika ada -lengkap yang ditetapkan di bawah pengurangan polinomial-waktu banyak-satu, maka . (Lihat " Set lengkap lengkap untuk NP: Solusi dugaan Berman dan Hartmanis ")$NP$$P = NP$

Adakah konsekuensi yang diketahui dari keberadaan set lengkap yang jarang untuk kelas kompleksitas lainnya? Khususnya, jika ada set lengkap -lengkap di bawah redspace banyak-satu, apakah itu menyiratkan ?$P$$P = L$

Ya, apa yang Anda disarankan adalah benar: jika ada jarang set -Lengkap bawah log-ruang banyak-satu pengurangan, maka P = L . Ini dugaan oleh Hartmanis pada tahun 1978 dan dibuktikan oleh Cai dan Sivakumar pada tahun 1995. Lihat makalah ini .$\mathbf{P}$$\mathbf{P} = \mathbf{L}$

$\mathbf{NL}$$\mathbf{NL} = \mathbf{L}$