Reduksi karp adalah waktu polinomial yang dapat dihitung banyak-satu pengurangan antara dua masalah komputasi. Banyak pengurangan Karp sebenarnya adalah fungsi satu-satu. Hal ini menimbulkan pertanyaan apakah setiap pengurangan Karp bersifat injeksi (fungsi satu-satu).
Apakah ada alam masalah -Lengkap yang dikenal menjadi lengkap hanya di bawah banyak-satu pengurangan Karp dan tidak diketahui lengkap di bawah pengurangan Karp injective? Apa yang kita mendapatkan (dan kalah) jika kita mendefinisikan N P menggunakan pengurangan Karp injective -completeness?
Satu keuntungan yang jelas adalah bahwa set jarang tidak dapat diselesaikan di bawah pengurangan Karp injeksi.
cc.complexity-theory
Mohammad Al-Turkistany
sumber
sumber
Jawaban:
sumber
Bahkan, bahkan contoh tandingan potensial "tidak wajar" untuk dugaan Isomorfisme - set k-kreatif dari Teorema 2.2 dan Joseph Young - lengkap di bawah satu-satu pengurangan oleh konstruksi.
[Diulang dari komentar saya di sini :] Karena kebanyakan reduksi yang kita buat sebenarnya adalah reduksi one-one, mengapa kita tidak mempelajarinya ketika secara formal lebih kuat dan kita mendapatkan sebagian besar waktu? Saya pikir karena lebih mudah untuk tidak perlu repot membuktikan suntikan, meskipun kita biasanya memilikinya. Dalam pengertian itu, mungkin banyak orang yang melakukan pengurangan adalah semacam "pengurangan Goldilocks", kekuatan yang tepat, kesederhanaan yang tepat untuk pembuktian.
sumber
Sebenarnya, pengurangan injeksi berguna dalam kriptografi. Misalkan Anda memiliki sistem bukti ZK untuk relasi NP R atas bahasa L. Jika Anda ingin membuat bukti ZK untuk relasi NP lain R 'di atas bahasa L', Anda harus menemukan dua fungsi f dan g dengan properti berikut : 1. x milik L 'iff f (x) milik L, 2. Jika (x, w) milik R' maka (f (x), g (x, w)) milik R. 3. Selain itu , f dan g harus dapat dihitung secara efisien.
Properti di atas menyiratkan bahwa jika sistem bukti untuk R lengkap dan suara, sistem bukti untuk R '(didefinisikan dengan cara yang jelas menggunakan fungsi-fungsi di atas untuk mengurangi contoh hubungan dengan yang lain) selesai dan sehat juga.
Bagaimana dengan membuktikan bahwa sistem yang baru juga ZK atau saksi-bisa dibedakan (WI)? Jika f tidak dapat dibalik, Anda dapat membuktikan bahwa sistem bukti yang diperoleh adalah ZK. Kalau tidak, untuk membuktikan bahwa Anda harus mengasumsikan bahwa sistem bukti untuk R adalah ZK input tambahan (bukan hanya ZK). Untuk WI, jika f tidak dapat dibalik, Anda dapat membuktikan bahwa sistem bukti untuk R 'adalah WI. Tanpa fakta bahwa f tidak dapat dibalik, saya tidak yakin apakah Anda dapat membuktikannya
sumber