Algoritma apa yang ada untuk memecahkan sistem linear bilangan alami?

9

Saya melihat masalah berikut:

Dengan -vektor dimensi bilangan asli dan beberapa vektor input , apakah kombinasi linear dari dengan koefisien bilangan alami?nv1,...,vmkamukamuvsaya

yaitu apakah ada beberapa mana ?t1,,tmNu=t1v1++tmvm

Jelas versi bilangan real dari masalah ini dapat diselesaikan dengan menggunakan eliminasi Gaussian. Saya bertanya-tanya, apakah versi bilangan bulat dari masalah ini telah dipelajari? Algoritma apa yang ada untuk menyelesaikannya?

Perhatikan bahwa ini menggunakan bilangan asli, tetapi bukan aritmatika modular, jadi ini agak terpisah dari Teorema Sisa Tiongkok dan sistem seperti itu. Juga, tampaknya terkait dengan persamaan Diophantine, tapi saya bertanya-tanya apa yang telah dilakukan dalam kasus di mana hanya bilangan bulat non-negatif yang dipertimbangkan? Ini juga mengingatkan pada masalah subset-sum multi-dimensi, digeneralisasi untuk memungkinkan kita mengambil jumlah salinan setiap vektor secara sewenang-wenang. Tampaknya juga terkait dengan pengujian apakah adalah elemen kisi yang dihasilkan oleh , kecuali bahwa di sini kami hanya mengizinkan kombinasi linear dengan koefisien non-negatif.uv1,,vm

Bagi siapa pun yang tertarik, ini dimotivasi dengan melihat apakah vektor Parikh dalam set linier, seperti dalam Teorema Parikh .

Secara khusus, saya tertarik pada algoritma yang bisa menyelesaikan masalah hanya menggunakan operasi bilangan alami, menghindari masuk ke angka real / floating point.

Ya ampun
sumber
2
Ya, versi integer (dan berbagai versi teori dering) telah dipelajari. Versi integer dapat diselesaikan dengan eliminasi Gaussian. Versi bilangan alami adalah binatang yang berbeda. Perasaan saya adalah bahwa itu harus NP-lengkap.
Thomas Klimpel
Bagaimana bisa NP-lengkap jika diselesaikan dengan eliminasi Gaussian? Saya masih tertarik pada algoritma untuk itu, bahkan jika itu merupakan masalah yang sulit dipecahkan.
jmite
Perhatikan juga bahwa dalam masalah yang saya lihat, sistem mungkin tidak dapat ditentukan, yaitu . Tidak yakin bagaimana ini mengubahnya. m<n
jmite

Jawaban:

9

Masalah Anda adalah NP-complete, dengan reduksi dari Subset Sum (ini ada di NP karena fakta bahwa semuanya non-negatif membatasi koefisien solusi dengan cukup baik). Diberikan instance dari Subset Sum (apakah ada subset dari S yang menjumlahkan ke T ?), Kami membuat sebuah instance v 1 , , v 2 n , u dari masalah Anda sebagai mengikuti. Untuk setiap 1 i n , kami menempatkan v iS={s1,,sn},TSTv1,,v2n,u1invimenjadi vektor dengan dua entri bukan nol: dan v i , n + 1 = s i , dan v n + i menjadi vektor dengan entri bukan nol yang unik v n + i , i = 1 . Vektor target u = 1 , ... , 1 , T . Setiap kombinasi alami dari v 1 , , v 2 nvi,i=1vi,n+1=sivn+ivn+i,i=1u=1,,1,Tv1,,v2nsama dengan harus memilih tepat satu dari masing-masing v i , v n + i , dan karenanya mengkodekan subset dari S yang penjumlahannya adalah nilai dari komponen terakhir.1,,1,vi,vn+iS

Yuval Filmus
sumber
Menarik. Apakah Anda menemukan bukti ini, atau Anda punya referensi untuk itu yang bisa saya kutip? Either way, terima kasih!
jmite
1
@iteite saya baru saja menemukan buktinya, meskipun saya tidak bisa mengesampingkan telah melihatnya.
Yuval Filmus