P dengan oracle faktorisasi bilangan bulat

18

Saya baru saja membaca pertanyaan " Apakah faktorisasi bilangan bulat merupakan masalah NP-complete? " ... jadi saya memutuskan untuk menghabiskan sebagian dari reputasi saya :-) mengajukan pertanyaan lain memiliki : $Q$ $P(\text{Q is trivial}) \approx 1$

Jika adalah oracle yang memecahkan faktorisasi bilangan bulat, apa kekuatan ? $A$ $P^A$

Saya pikir itu membuat kriptografi kunci publik berbasis RSA tidak aman ... tetapi selain itu, apakah ada hasil luar biasa lainnya?

cc.complexity-theory oracles factoring Marzio De Biasi
sumber

3

@ Untuk bagian itu P(Q is trivial)=1adalah lelucon, bukan?

Pratik Deoghare

Pertanyaan ini menyarankan pertanyaan terkait dan (mungkin) lebih alami: jika R adalah oracle yang mengembalikan f _ (_ M , n ) sebagai runtime maksimal dari mesin Turing polinomial-waktu M atas semua input panjang n , apa kekuatan dari P ^ R?

John Sidles

2

@Vor: Bukankah ini sama dengan bertanya "Masalah mana yang bisa menjadi polinomial waktu Turing dikurangi menjadi faktorisasi bilangan bulat?" Atau apakah Anda bermaksud untuk menanyakan hal lain?

Joshua Grochow

Saya seorang pemula, jadi pertanyaan saya hampir merupakan keingintahuan. Semua berawal dari sebuah pemikiran sederhana: keluar "di dunia nyata" Saya melihat banyak masalah NP-lengkap (tukang pos mencoba untuk menyimpan kekuatannya, sebuah keluarga yang bergerak dan ingin menyesuaikan furniturnya di truk, ...: - ))). Tapi saya tidak melihat "masalah anjak piutang" ... meskipun mereka MUNGKIN lebih sederhana (antara P dan NPC). ... mungkin kenyataan membenci multiplikasi :-D :-D

Marzio De Biasi

1

Lihat juga Konsekuensi Anjak Pi berada di P?

Jukka Suomela

11

Saya tidak punya jawaban untuk pertanyaan Anda, tetapi saya tahu bahwa gagasan serupa baru-baru ini dipelajari, dengan nama "keamanan berbasis malaikat."

Makalah pertama yang mempelajari konsep ini adalah Prabhakaran & Sahai (STOC '04) . Secara khusus, mereka menulis dalam abstrak:

[... kami memberikan] akses musuh ke kekuatan komputasi super-polinomial.

Makalah penting lain yang membahas gagasan ini adalah bahwa Canetti, Lin, & Pass (FOCS 2010) . Saya menyaksikan beberapa bagian dari presentasi konferensi mereka (di techtalks ), dan jika saya ingat dengan benar, mereka mulai dengan contoh yang mirip dengan apa yang Anda sebutkan dalam pertanyaan.

MS Dousti
sumber

13

Jelas setiap masalah keputusan yang dapat direduksi menjadi anjak piutang dapat diselesaikan dengan anjak anjak piutang. Tetapi karena kita diberi kemampuan untuk membuat beberapa kueri, saya mencoba memikirkan masalah non-sepele yang ingin dibuatkan beberapa kueri.

Masalah komputasi fungsi totient Euler tampaknya seperti masalah seperti itu. Saya tidak tahu bagaimana menyelesaikan versi keputusan dari masalah ini dengan pengurangan Karp ke versi keputusan anjak piutang. Tetapi dengan pengurangan Turing, mudah untuk mengurangi ini menjadi anjak piutang.

Robin Kothari
sumber

3

Berikut ini adalah posting terkait di MO mengenai kompleksitas komputasi fungsi totient.

Hsien-Chih Chang 張顯之

Tambahan kecil: ada juga pengurangan waktu polinomial ke arah lain, menghitung fungsi Totient Euler -> Anjak. Saya belum memeriksa apakah pengurangan diketahui bekerja untuk versi keputusan dari masalah ini. Tetap saja, mampu menghitung fungsi Totient (atau bahkan kelipatannya yang tetap) memberi Anda kemampuan untuk membuat faktor. Buku Shoup mendedikasikan satu bab untuk ini.

Juan Bermejo Vega

9

Mengelaborasi pada jawaban Joe sebelumnya: catatan yang . Yang terakhir adalah terendah kedua kelas dalam hirarki "rendah" : yang mengatakan bahwa . Ini berarti khususnya yang Kami dapat membuat pernyataan serupa untuk dan $\textrm{FACTORING} \in \mathsf{NP \cap coNP}$ $\mathsf{NP^{NP \cap coNP} = NP}$

P^{PABRIK} \subseteq N P^{PABRIK} \subseteq N P .

$\mathsf{P^{\textrm{FACTORING}} \subseteq NP^{\textrm{FACTORING}}} \subseteq \mathsf{NP}.$

c o N P

$\mathsf{coNP}$

B Q P

$\mathsf{BQP}$ , Untuk menunjukkan bahwa setidaknya pada tingkat kasar-grained,

memiliki batas kompleksitas yang sama sebagai masalah

itu sendiri, yang berarti

P^{FACTORING}

$\mathsf P^{\textrm{FACTORING}}$

FACTORING

$\textrm{FACTORING}$

P^{PABRIK} \subseteq N P \cap c Hai N P \cap B Q P .

$\mathsf{P^{\textrm{FACTORING}} \subseteq NP \cap coNP \cap BQP}.$

Niel de Beaudrap
sumber

N P \cap c o N P

$NP \cap coNP$

3

U P \cap c o U P

$\mathsf{UP} \cap \mathsf{coUP}$

6

$P^A\subseteq \Delta_2^P$

Marcus Ritt
sumber

5

$\mbox{FNP}$ $P \subseteq P^A \subseteq \Delta_2^p$ $P^{NP}$ $\mbox{BQP}$ $P \subseteq P^A \subseteq P^{NP \cap BQP}$

Joe Fitzsimons
sumber

P dengan oracle faktorisasi bilangan bulat

Jawaban: