Mengapa tidak mengambil representasi angka-angka dalam algoritma numerik?

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).$n-1$$n$ $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.$x$$x = \log n$$n = 2^x$$2^x$

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?$n$$x=n$

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

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 .

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=\{w_1, \ldots, w_n\}$$k$$O(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 $k$$100$$100$$k$$2^{100}-1$$k$$k$$2^{100}-1$

$n$$n$$p(n)$$k$$p(n)$$k$$2^{p(n)}-1$$k$$k$

$n$$k$

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)

$x$$x$$O(2^n)$

$Tally/Unary$$O(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.