Mengapa FACTOR ada dalam Co-NP?

12

Saya mengalami kesulitan membungkus kepala saya di sekitar masalah PRIME, KOMPOSIT, FAKTOR dan bagaimana mereka terkait dalam hal kompleksitas. Saya mengerti bahwa PRIME telah terbukti berada di oleh tes primality AKS, dan saya percaya ini juga berfungsi untuk COMPOSITE. $P$

Adapun FAKTOR,

F A C T O R = {(m, r) : \exists s such that 1 < s < r and s divides m}

$FACTOR = \{(m,r) :\;\; \exists s \text{ such that} 1<s<r \text{ and } s \text{ divides } m\}$

dari apa yang saya baca tampaknya bahwa itu adalah di . Saya melihat bahwa dalam sejak sertifikat akan terdiri dari pembagi prima dari kurang dari . Tetapi jenis sertifikat apa yang dapat menetapkan bahwa tidak ada pembagi utama (dalam waktu polinomial)? $NP \cap Co-NP$ $NP$ $m$ $r$

complexity-theory factoring Fequish
sumber

1

Untuk bahasa yang menjadi bukti NP bahwa input milik bahasa harus memiliki sertifikat yang dapat diverifikasi dalam waktu polinomial. Itu tidak berarti bahwa sertifikat untuk input yang bukan milik bahasa ada yang dapat diverifikasi secara efisien.

sashas

2

lihat juga NP varian lengkap anjak piutang / Theoretical Computer Science

vzn

11

$m$ $r$ $m$ $m$ $r$

Yuval Filmus
sumber

1

Terima kasih. Dan apakah saya mengerti dengan benar bahwa algoritma AKS dapat memberi tahu kami apakah suatu bilangan prima atau tidak dalam waktu polinomial, tetapi jika bukan bilangan prima, ia tidak memberi tahu kita faktor-faktornya?

Fequish

1

@Fequish: Jika tidak prima maka AKS tidak memberi tahu kami faktornya.

2

e^{O ((\log n)^{1 / 3} (\log \log n)^{2 / 3})}

$e^{O((\log n)^{1/3}(\log\log n)^{2/3})}$

n

$n$

5

Untuk menambah jawaban Yuval: pengujian primitif AKS ditemukan pada tahun 2002. Sebelumnya kami tidak memiliki algoritma waktu polinomial untuk memeriksa apakah suatu bilangan prima. Namun Pratt menemukan pada tahun 1975 apa yang sekarang dikenal sebagai sertifikat Pratt untuk primality dan membuktikan bahwa Primes ada di NP. Kami dapat menyertakan sertifikat primitif Pratt ini untuk faktor-faktor dalam sertifikat kami untuk menunjukkan bahwa FACTOR ada di dalam TNN menggantikan menggunakan algoritma AKS untuk memeriksa apakah faktor-faktornya prima secara langsung.

Denis Pankratov
sumber

3

Sertifikat resmi di Wikipedia

Kaveh

Mengapa FACTOR ada dalam Co-NP?

Jawaban: