Apakah kompleksitas masalah NP-hard atau -complete berubah ketika input mereka tidak dikodekan?

12

Apakah kesulitan masalah NP-hard atau NP-complete (seperti misalnya didefinisikan di sini ) berubah ketika inputnya unary bukan binary encoded?

Apa bedanya jika input dari masalah NP-hard sangat tidak terenkripsi? Maksud saya, jika saya mengambil contoh masalah Knapsack NP-complete yang lemah, itu adalah NP-complete ketika biner dikodekan tetapi dapat diselesaikan dalam waktu polinomial dengan pemrograman dinamis ketika unary dikodekan. Mungkin itu memiliki beberapa implikasi untuk kekerasan tingkat yang lebih tinggi dari hirarki waktu polinomial?

Apakah gagasan kuat ...- keras juga berlaku untuk kelas kompleksitas lainnya, misalnya kelas hierarki waktu polinomial yang lebih tinggi?

Saya sebelumnya menanyakan pertanyaan ini di stackoverflow.com tetapi ditunjukkan bahwa lebih tepat di sini.

complexity-theory time-complexity np-complete pengguna2145167
sumber
Haruskah saya mengajukan pertanyaan ini dengan lebih baik di cstheory.stackexchange.com ? Aku hanya tidak tahu itu ada. Para aswers di sini tidak pergi ke arah yang saya harapkan.
user2145167
Kenapa tidak? Mereka (sejauh yang saya tahu) benar, jadi mungkin pertanyaan Anda bukan yang ingin Anda tanyakan? Selain itu, Ilmu Komputer Teoretis adalah untuk pertanyaan TCS tingkat penelitian , yang tentu saja tidak.
Raphael

Jawaban:

4

Ukuran masalah dikodekan dalam unary adalah ukuran dan jika biner. Jika waktu yang diambil adalah , ini adalah dalam kasus pertama dan dalam kasus kedua. Jadi suatu algoritma yang polinomial untuk kasus pertama mungkin akan eksponensial untuk yang kedua. Pengkodean masalah dapat mengubah kompleksitas suatu algoritma secara radikal.NNlog⁡NF(N)F(size)F(2size)

vonbrand
sumber
3

Tidak.

Jika Anda mengubah pengkodean input, Anda telah mengubah definisi formal masalah, yang berarti masalah yang berbeda . Kompleksitas masalah asli tidak berubah, karena alasan yang sama bahwa menunjuk pada cahaya berbeda di langit tidak mengubah massa bulan.

JeffE
sumber
2
Saya pikir pertanyaannya adalah apakah untuk masalah NP-hard versi unary bukan NP-hard. PP1
Raphael
2

Jawaban singkatnya adalah, bahwa jika inputnya disandikan, maka itu lebih panjang . Secara eksponensial lebih lama. Sekarang, sebuah algoritma yang bekerja dalam waktu polinomial dalam ukuran input memiliki "cukup waktu" untuk menyelesaikan masalah, hanya karena input itu sendiri secara eksponensial lebih lama daripada dalam masalah aslinya.

Ran G.
sumber
1

Melihat melewati masalah formulasi yang ditunjukkan dalam jawaban JeffE, jawabannya adalah ya.

Pertimbangkan masalah Knapsack . Itu memang memiliki algoritma pseudo-polinomial , yaitu satu dengan runtime yang dibatasi oleh polinomial dalam angka yang dikodekan dalam input. Karena dalam nilai-nilai pengkodean unary sesuai dengan panjang, ini adalah algoritma waktu polinomial untuk versi unary.

Faktanya, setiap masalah NP-complete yang lemah termasuk dalam kategori ini.

Raphael
sumber
Pertanyaan sampingan, tapi saya tidak pernah mengerti - bagaimana Anda bahkan "menyandikan" sesuatu di unary? Tidakkah kamu membutuhkan pembatas?
user541686
@Mehrdad Ya dan tidak. Iya; simbol pemisahan biasanya tidak dihitung dalam hal ini, cf juga input vs alfabet tape; di sini kami hanya mempertimbangkan ukuran alfabet input. Tidak; pada prinsipnya, satu angka cukup untuk menyandikan tupel dan himpunan angka yang dapat dihitung sehingga Anda tidak perlu simbol pemisahan. Itu jelas tidak berguna untuk "bekerja" dengan mesin seperti itu tetapi dibenarkan mengabaikan simbol pemisahan (dan kontrol lainnya).
Raphael
Hmm ... Saya tidak yakin saya mengerti bagian "tidak" Anda; bagaimana Anda tahu di mana nomor itu berakhir jika Anda tidak memiliki pemisah di akhir? Sepertinya sedikit seperti logika melingkar bagi saya: jika kita mengabaikan pemisah, maka secara efektif pertanyaannya menjadi "jika kita memaksa input untuk mengambil lebih banyak ruang secara eksponensial, apakah itu mengubah waktu berjalan dari algoritma eksponensial relatif terhadap ukuran input ? " yang jawabannya adalah sepele ya ... menurut definisi. Ini tidak begitu banyak mengubah pengkodean karena secara artifisial menambahkan bit yang berlebihan begitu Anda memperhitungkan separator.
user541686
@Mehrdad Oke, saya hanya berpikir tentang memisahkan beberapa angka dari satu sama lain. Dalam hal apa pun, Anda memerlukan resp penanda akhir. simbol "kosong" pada mesin Turing; Anda tidak dapat menyingkirkannya. Sisanya Anda dapat menyandikan ke satu nomor (pada penalti runtime, jelas).
Raphael