Apakah NP-hardness menyiratkan P-hardness?

22

Jika masalah adalah NP-hard (menggunakan pengurangan waktu polinomial), apakah itu menyiratkan bahwa itu P-hard (menggunakan ruang log atau reduksi NC)? Tampaknya intuitif bahwa jika itu sama sulitnya dengan masalah apa pun di NP maka harus sama sulitnya dengan masalah apa pun di P, tapi saya tidak melihat cara mengaitkan reduksi dan mendapatkan pengurangan ruang log (atau NC).

cc.complexity-theory np-hardness Adam Crume
sumber
4
Ini berlaku jika Anda menggunakan jenis yang sama pengurangan bagi kedua belah pihak, misalnya masalah wrt pengurangan log-ruang juga P - h a r d pengurangan wrt log-ruang. NP−hardP−hard
Kaveh
yaitu intuisi Anda benar tetapi pertanyaan yang Anda ajukan meminta lebih dari itu (karena Anda menggunakan berbagai jenis pengurangan).
Kaveh
1
Bagian terpenting dari pertanyaan adalah gagasan tentang reducibilitas yang Anda gunakan, tetapi informasi ini entah bagaimana dimasukkan ke dalam tanda kurung seolah-olah itu adalah informasi yang paling tidak penting!
Tsuyoshi Ito

Jawaban:

31

Tidak ada implikasi seperti itu yang diketahui. Khususnya mungkin bahwa dalam hal ini semua masalah (termasuk yang sepele) adalah NP-hard di bawah pengurangan waktu-poli (karena pengurangan hanya dapat menyelesaikan masalah), tetapi yang sepele (khususnya yang terletak pada L) pasti bukan P-hard di bawah pengurangan logspace (seperti sebaliknya L = P). L≠P=NP

Hal yang sama berlaku untuk NC, bukan L.

Noam
sumber
3
Terima kasih banyak atas jawaban ini. Saya pikir untuk banyak orang - dan setidaknya bagi saya - pertanyaan ini sepertinya bukan masalah besar, tetapi setelah membaca jawaban tiga kalimat Anda, itu "jelas" dalam. (Juga, terima kasih atas pertanyaannya, @Adam Crume.)
Aaron Sterling