Pertanyaan dalam teori bilangan
Kita tahu bahwa fungsi eksponensial atas bilangan asli tidak dapat dihitung dalam waktu polinomial, karena ukuran output tidak dibatasi secara polinomi dalam ukuran input.exp( x , y) = xyexp(x,y)=xy\exp(x,y) = x^y Apakah ini alasan utama untuk kesulitan menghitung fungsi eksponensial, atau apakah...
Baru-baru ini Gil Kalai dan Dick Lipton keduanya menulis artikel yang bagus tentang dugaan menarik yang diusulkan oleh Peter Sarnak, seorang ahli dalam teori bilangan dan Hipotesis Riemann. Dugaan. Biarkan menjadi fungsi Möbius . Misalkan adalah fungsi dengan input dalam bentuk representasi...
Pertimbangkan masalah penghitungan berikut (atau masalah keputusan terkait): Diberi dua bilangan bulat positif yang dikodekan dalam biner, hitung pembagi bersama terbesarnya (gcd). Apa kelas kompleksitas terkecil dari masalah ini? Bisakah Anda memberikan referensi? Dalam pertanyaan ini saya...
Setiap bilangan alami dapat dianggap sebagai urutan bit, jadi memasukkan bilangan alami sama dengan memasukkan urutan 0-1, sehingga masalah NP-lengkap dengan input alami jelas ada. Tetapi apakah ada masalah alami, yaitu masalah yang tidak menggunakan beberapa pengkodean dan interpretasi khusus dari...
Diberikan bilangan bulat dengan panjang n bit, seberapa sulitkah untuk menampilkan jumlah faktor utama (atau jumlah faktor) dari N ?NNNnnnNNN Jika kita tahu faktorisasi utama NNN , maka ini akan mudah. Namun, jika kita mengetahui jumlah faktor prima, atau jumlah faktor umum, tidak jelas...
Apakah algoritme waktu polinomial deterministik yang dikenal untuk masalah berikut: Input: angka alami nnn (dalam pengkodean biner) Output: bilangan prima p>np>np > n . (Menurut daftar masalah terbuka oleh Leonard Adleman, masalahnya terbuka pada 1995.)
Apa yang diketahui tentang kompleksitas komputasi bilangan bulat anjak di bidang bilangan umum? Lebih spesifik: Melalui bilangan bulat, kami mewakili bilangan bulat melalui ekspansi binernya. Apa representasi analog dari bilangan bulat di bidang bilangan umum? Apakah diketahui bahwa keutamaan...
Apa implikasi yang akan menjadi bukti dugaan abc untuk
Langkah pertama dari algoritma pengujian primality AKS adalah untuk memeriksa apakah nomor input adalah kekuatan yang sempurna. Tampaknya ini adalah fakta yang terkenal dalam teori bilangan karena makalah ini tidak menjelaskannya secara terperinci. Dapatkah seseorang memberi tahu saya bagaimana...
Ingat jumlah bilangan prima adalah fungsi penghitungan utama . Dengan "PRIMES dalam P", komputasi ada di #P. Apakah masalahnya # P-selesai? Atau, mungkin, ada alasan kerumitan untuk percaya bahwa masalah ini bukan # P-complete? π(n)π(n)\pi(n)≤n≤n\le nπ(n)π(n)\pi(n) PS Saya menyadari ini agak naif...
Wikipedia memberikan contoh masalah di mana versi penghitungannya sulit, sedangkan versi keputusannya mudah. Beberapa di antaranya menghitung kecocokan sempurna, menghitung jumlah solusi untuk -SAT dan jumlah penyortiran topologi.222 Apakah ada kelas penting lainnya (misalnya contoh dalam kisi,...
Saya tertarik pada kompleksitas penyelesaian persamaan linear modulo k , untuk arbitrary k (dan dengan minat khusus pada kekuatan utama), khususnya: Masalah. Untuk sistem tertentu mmm linear persamaan di nnn tidak diketahui modulo kkk , jangan terdapat solusi? Dalam abstrak untuk makalah...
Dalam makalahnya tahun 1995, Algoritma Polinomial-Waktu untuk Faktorisasi Utama dan Logaritma Terpisah pada Komputer Quantum , Peter W. Shor membahas peningkatan pada bagian pencarian-urutan dari algoritma faktorisasi-nya. Output algoritma standar r′r′r' , pembagi dari urutan rrr dari xxx modulo...
Saya bertanya-tanya apakah ada bibliografi yang baik tentang upaya untuk menyelidiki dugaan Collatz sebagai tata bahasa formal? (atau upaya lain apa pun dalam komunitas CS untuk menangani kelas fenomena generatif ini & sifat "tersendat"
Dari komentar di salah satu pertanyaan saya di MathOverflow saya mendapatkan perasaan bahwa pertanyaan mengenai GCD berada di vs P ini mirip dengan pertanyaan mengenai Integer faktorisasi berada di P vs N P .N CNC\mathsf{NC}PP\mathsf{P}PP\mathsf{P}N PNP\mathsf{NP} Apakah ada sesuatu seperti...
Saya tertarik pada masalah "terdekat" (dan "paling kompleks") dengan dugaan Collatz yang telah berhasil diselesaikan (yang menurut Erdos terkenal "matematika belum matang untuk masalah seperti itu"). Telah terbukti bahwa kelas masalah "Collatz-like" tidak dapat diputuskan. Namun, masalah yang...
Apa kerumitan dalam menentukan apakah suatu interval bilangan asli mengandung bilangan prima? Varian Saringan Eratosthenes memberikan algoritma , di mana adalah panjang interval dan menyembunyikan menyembunyikan faktor polar-logaritmik di titik awal interval; dapatkah kita berbuat lebih baik (dalam...
Pertimbangkan masalah tes keanggotaan abelian-subkelompok berikut ini . Input: Sebuah kelompok abelian berhingga dengan sewenang-wenang-besar .G=Zd1×Zd1…×ZdmG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}didid_i Sebuah pembangkit-set dari subkelompok...
'Diberikan a,b,c∈Na,b,c∈Na,b,c\in\Bbb N , apakah ada x,y∈Nx,y∈Nx,y\in\Bbb N , ax2+by=cax2+by=cax^2+by=c ' adalah NPNP\mathsf{NP} -complete. Kelas kompleksitas mana yang 'Diberikan , adakah x , y ∈ N , a x 2 + b y 2 = c ' milik?a,b,c∈Na,b,c∈Na,b,c\in\Bbb Nx,y∈Nx,y∈Nx,y\in\Bbb...
SebuahaabbbSebuahaabbbSebuahaabbbO ( m logm logcatatanm )O(mlogmloglogm)O(m\log m\log\log m)mmmΩ ( m log m log log m )max{a,b}max{a,b}\max\{a,b\}Ω(mlogmloglogm)Ω(mlogmloglogm)\Omega(m\log m\log\log m) batas bawah dari masalah ini? Terima kasih dan salam, dan maaf jika ini pertanyaan...