Mengapa tidak mengambil representasi angka-angka dalam algoritma numerik?

15

Algoritma waktu semu-polinomial adalah algoritma yang memiliki waktu berjalan polinomial pada nilai input (besarnya) tetapi waktu berjalan eksponensial pada ukuran input (jumlah bit).

Misalnya menguji apakah angka n adalah prima atau tidak, memerlukan perulangan angka dari 2 ke dan memeriksa apakah mod bernilai nol atau tidak. Jika mod membutuhkan waktu O (1), kompleksitas waktu keseluruhan akan menjadi O (n).n1n i

Tetapi jika kita membiarkan menjadi jumlah bit yang diperlukan untuk menulis input maka (biner) jadi dan waktu berjalan dari masalahnya adalah O ( ) yang eksponensial.xx=lognn=2x2x

Pertanyaan saya adalah, jika kita menganggap representasi input unary , maka selalu dan kemudian waktu semu-polinomial akan sama dengan kompleksitas waktu polinomial. Jadi mengapa kita tidak pernah melakukan ini?nx=n

Lebih jauh lagi karena ada algoritma waktu pseudo-polinomial untuk knapsack, dengan mengambil , knapsack akan polinomial sebagai hasilnya P = NPx=n

M ama D
sumber
3
Sebenarnya, kami melakukan ini, hanya tidak cukup sering. Untuk alasan yang sama kita biasanya tidak berurusan dengan bahasa unary, tetapi ada banyak hasil menarik terkait dengan binatang buas ini. Sudahkah Anda memeriksanya?
André Souza Lemos
2
Ya, jika Anda menghilangkan perbedaan antara ukuran dan besarnya, Anda kehilangan semua konsep yang didasarkan pada perbedaan itu.
André Souza Lemos
7
Karena itu menempatkan iblis ke dalam gaun yang bagus. Itu tidak membuat apa pun lebih cepat, itu hanya membuat "kompleksitas waktu berjalan" tidak berarti.
Raphael
4
@Drupalist Masalah knapsack unary sebenarnya tidak dikenal sebagai NP-complete karena reduksi normal ke knapsack mengasumsikan bahwa angka-angka ditulis dalam biner. Jika Anda mencoba melakukan reduksi standar tetapi menulis angka dalam unary, reduksi tidak dapat dihitung dalam waktu polinomial. Akibatnya, masalah knapsack unary yang dipecahkan dalam waktu polinomial tidak akan berarti bahwa P = NP.
templatetypedef
2
Anda mungkin ingin memeriksa jawaban lain yang ditandai pseudo-polinomial , khususnya yang ini .
Raphael

Jawaban:

17

Apa artinya ini adalah bahwa ransel unary ada dalam P. Itu tidak berarti ransel itu (dengan angka-angka yang disandikan biner) ada dalam P.

Knapsack dikenal sebagai NP-complete. Jika Anda menunjukkan bahwa ransel ada di P, itu akan menunjukkan bahwa P = NP.

Tapi Anda belum menunjukkan bahwa ransel di P. Anda telah menunjukkan bahwa ransel unary di P. Namun, ransel unary tidak dikenal sebagai NP-lengkap (memang, kecurigaan standar adalah bahwa kemungkinan besar itu tidak lengkap NP ). Oleh karena itu, meletakkan ransel unary di P tidak menyiratkan bahwa P = NP.


Jadi masalah apa yang harus kita perhatikan, ransel atau ransel unary? Jika motivasi Anda didasarkan pada masalah praktis, maka jawabannya akan tergantung pada ukuran angka yang ingin Anda selesaikan dengan masalah ransel: jika jumlahnya besar, maka Anda tentu lebih peduli pada ransel daripada ransel biasa. Jika motivasi Anda didasarkan pada masalah teoretis, maka knapsack bisa dibilang lebih menarik, karena itu memungkinkan kita untuk mendapatkan pemahaman yang lebih dalam - itu memungkinkan kita untuk membuat perbedaan antara ukuran vs besarnya - sedangkan knapsack unary mencegah kita membuat perbedaan itu.


Untuk menjawab pertanyaan tindak lanjut tentang algoritma pemrograman dinamis untuk masalah ransel:

Ya, algoritme pemrograman dinamis yang sama dapat diterapkan ke ransel dan un ransel. Waktu menjalankannya adalah polinomial dalam besarnya angka, tetapi eksponensial (bukan polinomial) dalam panjang angka ketika dikodekan dalam biner. Jadi, waktu berjalannya adalah polinomial dalam panjang input ketika input dikodekan dalam unary tetapi tidak polinomial dalam panjang input ketika input dikodekan dalam biner. Itu sebabnya kami tidak menganggap algoritma pemrograman dinamis ini menjadi algoritma polinomial-waktu untuk ransel unary, tetapi tidak menganggap itu sebagai algoritma polinomial-waktu untuk ransel (binary-encoded).

Ingatlah bahwa kita mengatakan suatu algoritma berjalan dalam waktu polinomial jika waktu operasinya paling banyak adalah polinomial dari panjang input, dalam bit .

DW
sumber
1
Terima kasih banyak, saya tidak tahu bahwa kompleksitas kelas unary dan non-unary dari algoritma yang sama mungkin berbeda. Mengapa solusi pemrograman dinamis dari knapsack standar tidak dapat diterapkan pada knapsack unary, dan itu mengarah pada kelas kompleksitas yang berbeda? Saya mengalami masalah dengan memahami versi masalah yang tidak disadari.
M ama D
@Drupalist, saya sudah mengedit jawaban saya untuk menambahkan dua paragraf di akhir untuk menjawab pertanyaan itu.
DW
Terima kasih banyak, dari apa yang saya pahami perbedaan antara ukuran input dan besarnya adalah alasan perbedaan antara polinomial dan pseudo-polinomial, dengan menggunakan representasi unary saya mencoba menghilangkan perbedaan ini, Jika kita lupa ransel dan kembali ke angka algoritma, saya ingin tahu dengan menetapkan apa yang akan menjadi interpretasi polinomial dan pseudo-polinomial? Terima kasih lagix=n
M ama D
@Drupalist, saya tidak sepenuhnya yakin apa yang Anda maksud dengan mengatur , jadi saya tidak yakin bagaimana menjawabnya. Pada titik ini saya akan menyarankan yang terbaik untuk mengajukan pertanyaan baru (mandiri) (dan mendefinisikan semua variabel Anda dalam pertanyaan itu). Platform ini tidak begitu baik untuk pertanyaan tindak lanjut atau bolak-balik: cara terbaik yang kami miliki untuk mengatasinya adalah dengan mengajukan pertanyaan baru, berdasarkan apa yang telah Anda pelajari dari jawaban untuk pertanyaan ini. x=n
DW
1
@NikosM., OK, mengerti. Terima kasih untuk umpan baliknya. Secara pribadi, saya tidak percaya pernyataan itu salah, jadi saya akan membiarkannya apa adanya. (Alasan saya: Panjang input tidak tergantung pada pilihan representasi, jadi saya tidak percaya itu bertentangan dengan apa pun yang Anda tulis.) Namun, sangat mungkin perspektif saya mungkin terlalu sempit, atau bahwa penjelasan atau penjelasan yang lebih rinci dari perspektif yang berbeda mungkin menambah nilai. Jangan ragu untuk menulis jawaban tambahan atau menyarankan edit jika Anda merasa poin ini bisa lebih jelas.
DW
6

Saya akan menambahkan satu hal kecil ke jawaban DW:

Saya telah melihat orang-orang yang berpikir bahwa karena Knapsack unary dalam P maka kita dapat menggunakannya di tempat Knapsack yang algoritma saat ini terbaik memiliki waktu yang eksponensial.

Biarkan input menjadi dan k dan pertimbangkan algoritma pemrograman dinamis untuk Knapsack dan Knapsack unary. Waktu berjalan bagi mereka berdua adalah O ( n k ) . Ini adalah waktu berjalan yang sama. Yaitu jika Anda memiliki input, tidak masalah jika Anda menggunakan pemrograman dinamis untuk Knapsack unary atau pemrograman dinamis untuk Knapsack. Keduanya akan mengambil (kira-kira) jumlah waktu yang sama untuk menyelesaikan contoh masalah. Secara teoritis di mana saja Anda menggunakan yang Anda dapat menggunakan yang lain juga. Anda hanya perlu mengonversi angka dari unary ke binary dan sebaliknya.W={w1,,wn}kO(nk)

Jadi apa gunanya mendefinisikan kompleksitas algoritma wrt dengan ukuran input? Mengapa tidak selalu menyatakan mereka dalam hal parameter sebagai ?O(nk)

Jika Anda peduli tentang masalah dalam isolasi Anda dapat melakukannya. Sebenarnya itulah yang sering dilakukan orang dalam algoritma. Kompleksitas algoritma grafik sering dinyatakan dalam hal jumlah simpul dan jumlah tepi, bukan ukuran string yang mengkodekannya.

Tapi ini hanya ketika kita berurusan dengan masalah yang terisolasi. Ini tidak berguna ketika kita berurusan dengan masalah dengan berbagai jenis input. Untuk grafik kita dapat berbicara tentang menjalankan waktu wrt ke jumlah simpul dan tepi. Untuk Knapsack kita dapat berbicara tentang jumlah item dan ukuran Knapsack. Tetapi bagaimana jika kita ingin membicarakan keduanya? Misalnya ketika kita ingin reduksi antar masalah, atau mendiskusikan kelas masalah yang mencakup masalah arbitrer, bukan hanya masalah dengan grafik sebagai input. Kami membutuhkan parameter input universal. Input secara umum hanyalah string, kitalah yang menafsirkan simbolnya sebagai angka unary, angka biner, grafik, dll. Untuk mengembangkan teori umum kompleksitas algoritme dan masalah, kita memerlukan parameter input umum. Ukuran input adalah pilihan yang jelas dan ternyata cukup kuat sehingga kita dapat membangun teori yang masuk akal di atasnya. Itu bukan satu-satunya kemungkinan. Untuk yang artifisial kita dapat membangun teori berdasarkan dengan ukuran input. Ini akan bekerja dengan baik.2

Sekarang kita memutuskan untuk menggunakan ukuran sebagai parameter universal input kita memaksa untuk berpikir tentang pengkodean objek dalam hal string. Ada berbagai cara untuk menyandikannya dan ukurannya bisa berbeda. (Mereka juga membuat hal-hal yang berbeda mudah / sulit.) Dalam hal teori umum algoritma, apakah kita menyandikan nomor input dalam unary atau binary menjadi penting. Jika kita menggunakan unary dan ukuran adalah 100 , jumlah terbesar yang akan kita dapatkan adalah 100 . Jika kita menggunakan biner k bisa sebesar 2 100 - 1 . Jadi ketika kita berbicara tentang waktu berjalan menyelesaikan masalah Knapsack di mana ukuran kk100100k21001kk21001

nnp(n)kp(n)k2p(n)1kk

nk

Kaveh
sumber
Terima kasih banyak, satu pertanyaan lagi, dengan mengonversi input ke representasi unary-nya, apa yang akan terjadi dengan masalah menentukan apakah suatu bilangan prima atau tidak? Masalah ini polinomial berdasarkan pada besarnya input tetapi eksponensial berdasarkan bit input (seperti yang saya tunjukkan dalam pertanyaan), akankah konversi ini membuat sesuatu yang lebih baik?
M ama D
nO(n)nb=210241210241210241
Kaveh
klarifikasi yang bagus, namun lihat komentar saya di bawah jawaban DW yang terkait dengan posting ini
Nikos M.
2

Singkatnya dan sederhana, saya akan tunjukkan mengapa.

Tally

x = input integer

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

xxO(2n)

Tally/UnaryO(n)x

x = input tallies

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

Representasi input tidak membuat kode berjalan lebih cepat. Meskipun algoritma ke-2 benar-benar bersifat poli-waktu. Sangat tidak praktis dalam menemukan faktor untuk RSA.

Travis Wells
sumber
Contoh yang bagus, terima kasih
M ama D