Kelas kompleksitas mana yang dimiliki masalah teori bilangan ini?

'Diberikan $a,b,c\in\Bbb N$ , apakah ada $x,y\in\Bbb N$ , $ax^2+by=c$ ' adalah $\mathsf{NP}$ -complete.

Kelas kompleksitas mana yang 'Diberikan , adakah , ' milik? $a,b,c\in\Bbb N$ $x,y\in\Bbb N$ $ax^2+by^2=c$

ds.algorithms complexity-classes reductions nt.number-theory np-complete
sumber

Mengapa NP-masalah pertama selesai? Referensi akan dihargai. :)

Michael Wehar

@MichaelWehar, Quadratic Diophantine adalah NP-complete. Saya pikir itu bahkan di Gary dan Johnson.

Kaveh

Itu adalah AN8 di Garey dan Johnson, halaman 250: Manders and Adleman, "NP-menyelesaikan masalah keputusan untuk kuadratika biner", 1978.

Kaveh

Keberadaan solusi rasional secara polinomi dapat direduksi menjadi anjak piutang, maka dalam

: menggunakan prinsip Hasse , sama dengan memeriksa bahwa simbol Hilbert

untuk semua bilangan prima

N P \cap c o N P

$\mathrm{NP}\cap\mathrm{coNP}$

(a / c, b / c)_{p} = 1

$(a/c,b/c)_p=1$

p ∣ 2 a b c

$p\mid2abc$

Emil Jeřábek 3.0

Perhatikan bahwa (baik untuk bilangan bulat atau solvabilitas rasional) Anda tidak mungkin mendapatkan yang lebih baik daripada memfaktorkan: sudah menjadi kasus khusus

(yaitu, apakah

adalah jumlah dari dua kotak) bertanya apakah semua bilangan prima terjadi pada bahkan dengan multiplisitas, dan sejauh yang saya ketahui, tidak diketahui cara menguji ini lebih efisien daripada memfaktorkan ; lih. mathoverflow.net/q/57981 .

a = b = 1

$a=b=1$

c

$c$

p \equiv 3 (\mod 4)

$p\equiv3\pmod4$

c

$c$

c

$c$

Emil Jeřábek 3.0

Jawaban:

Ditambahkan kemudian: Seperti disebutkan dalam komentar, batas atas NP adalah sepele jika a, b, dan c positif, seperti yang diminta.

Teorema 1.2 dalam makalah ini menunjukkan bahwa memutuskan apakah persamaan diophantine yang diberikan dalam dua variabel memiliki solusinya adalah dalam NP.

Manu
sumber

Saya tidak mengatakan ini adalah jawaban yang baik (ini menyatakan yang jelas).

Ini sepertinya menjawab pertanyaan yang diajukan. Jika Anda ingin kondisi lebih lanjut, Anda harus memasukkannya dalam pertanyaan.

András Salamon

@ AndrásSalamon, tidak, batas atas NP tampaknya sepele ketika dan keduanya tidak negatif (jadi dan secara polinomi dibatasi oleh dalam , , dan ). Pertanyaan sebenarnya adalah apakah sulit untuk NP.

a

$a$

b

$b$

x

$x$

y

$y$

a

$a$

b

$b$

c

$c$

Kaveh

@ Kaveh: ya, tapi bukan itu yang ditanyakan. Selanjutnya, saya anggap a, b, c diberikan dalam biner, jadi x dan y hanya dibatasi secara eksponensial dalam n?

András Salamon

@ AndrásSalamon, Ukurannya dibatasi secara polinomi . Seperti yang saya katakan, berada di NP adalah masalah sepele. Makalah ini berbicara tentang kasus yang lebih umum yang bukan pertanyaannya.

n

$n$

Kaveh