Masalah yang status kepesertaannya tidak diketahui tetapi diketahui lebih sulit daripada masalah penghentian

Jawaban:

5

Dengan asumsi bahwa dengan "kurang keras" yang Anda maksudkan "dapat direduksi menjadi", maka masalah apa pun yang diketahui ada di dalamnya RE tetapi tidak diketahui berada di R memenuhi kondisi ini.

Sebagai contoh, ambil masalah PCP dengan 4 petak, yang kepatutannya terbuka. Ini adalah latihan yang mudah untuk mengurangi masalah (atau masalah lainnya dalam RE) menjadi HALT.

Shaull
sumber
2
Tidak diketahui bahwa HALT dapat direduksi menjadi PCP dengan 4 ubin . Yang terakhir adalah masalah terbuka.
Shaull
1
Disebutkan (saya menulis bahwa decidability tidak diketahui, disiratkan bahwa tidak ada pengurangan yang diketahui dari HALT).
Shaull