Apakah ada masalah alami pada naturals yang lengkap dengan NP?

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 digit? Misalnya "Is na prime?" adalah masalah alami, tetapi ini dalam P. Atau "Siapa yang memenangkan permainan Nim dengan tumpukan ukuran 3, 5, n, n?" adalah masalah lain yang saya anggap alami, tetapi kita juga tahu ini berada di P. Saya juga tertarik pada kelas kompleksitas lain, bukan NP.

Pembaruan: Seperti yang ditunjukkan oleh Emil Jeřábek, diberi untuk menentukan apakah memiliki solusi atas naturals adalah NP-complete. Inilah yang saya pikirkan sebagai sesuatu yang alami, kecuali bahwa di sini inputnya adalah tiga angka, bukan hanya satu.$a,b,c\in \mathbb N,$$ax^2+by-c=0$

Pembaruan 2: Dan setelah lebih dari empat tahun menunggu, Dan Brumleve telah memberikan solusi "lebih baik" - perhatikan bahwa itu masih belum lengkap karena pengurangan secara acak.

Masalah ini memiliki variasi dengan input integer tunggal:

Apakah memiliki pembagi secara ketat di antara dua faktor utama terbesarnya?$n$

Idenya adalah untuk menggunakan pengurangan acak yang sama dari jumlah bagian yang dijelaskan dalam jawaban teratas untuk pertanyaan terkait, tetapi dengan kisaran target yang dikodekan sebagai dua bilangan prima terbesar alih-alih diberikan secara terpisah. Definisi tersebut memiliki tampilan alami meskipun itu hanya fungsi berpasangan yang menyamar.

Berikut adalah variasi lain dari masalah yang sama, dengan pengurangan yang sama dari masalah partisi:

Apakah produk dari dua bilangan bulat yang berbeda kurang dari ?$n$$n^{\frac{1}{4}}$

Dalam kedua pengurangan tersebut kami "menyamarkan" serangkaian bilangan bulat dengan menemukan bilangan prima terdekat dan mengambil produk mereka. Jika mungkin untuk melakukan itu dalam waktu polinomial maka masalah ini selesai NP.

Saya pikir itu mencerahkan untuk melihat contoh-contoh ini bersama dengan teorema Mahaney : jika dan kita dapat menemukan bilangan prima terdekat, maka set ini tidak jarang. Sangat memuaskan untuk mendapatkan pernyataan aritmatika murni dari teori kompleksitas (meskipun itu hanya dugaan dan kemungkinan mudah dibuktikan dengan cara lain).$P \ne NP$

Berdasarkan diskusi, saya akan memposting ulang ini sebagai jawaban.

Sebagaimana dibuktikan oleh Manders dan Adleman , masalah berikut ini adalah NP-complete: diberikan bilangan asli , tentukan apakah ada bilangan alami sehingga .$a,b,c$$x\le c$$x^2\equiv a\pmod b$

Masalah dapat dipersamakan dinyatakan sebagai berikut: diberikan , menentukan apakah kuadrat memiliki solusi .$b,c\in\mathbb N$$x^2+by-c=0$$x,y\in\mathbb N$

(Makalah asli menyatakan masalah dengan , tetapi tidak sulit untuk melihat bahwa seseorang dapat menguranginya ke kasing )$ax^2+by-c$$a=1$

Berikut adalah lengkap dengan satu bilangan asli sebagai input.$\text{NEXP}$

Masalahnya adalah tentang memasang kisi-kisi dengan set tetap ubin dan batasan pada ubin yang berdekatan dan ubin pada batas. Semua ini adalah bagian dari spesifikasi masalah; itu bukan bagian dari input. Inputnya hanya angka . Masalahnya adalah -complete untuk beberapa pilihan aturan ubin seperti yang ditunjukkan pada$n \times n$$n$$\text{NEXP}$

D. Gottesman, S. Irani, "Kompleksitas Quantum dan Klasik dari Permasalahan Penerjemahan yang Berbeda dan Masalah Hamiltonian," Proc. 50 Tahunan Symp. tentang Yayasan Ilmu Komputer, 95-104 (2009), DOI: 10.1109 / FOCS.2009.22 . Juga arXiv: 0905.2419 .

Masalahnya didefinisikan pada halaman 5 dari versi arxiv.

Selain itu, mereka juga mendefinisikan masalah serupa yaitu -complete, yang merupakan analog quantum error-terikat dari . (Analog kesalahan terikat klasik adalah .)$\text{QMA}_\text{EXP}$$\text{NEXP}$$\text{NEXP}$$\text{MA}_\text{EXP}$

Saya pikir bahwa menggunakan salah satu varian kompleksitas Kolmogorov yang terikat waktu, Anda dapat membangun masalah yang hanya menggunakan representasi biner dari sebuah angka dan (saya pikir) tidak mungkin berada di ; secara tidak resmi itu adalah versi masalah yang dapat ditentukan "Apakah kompresibel?":$\mathsf{P}$$n$

Masalah: Diberikan , apakah mesin Turing ada sedemikian rupa sehingga dan pada kaset kosong menghasilkan dalam kurang dari langkah, di mana adalah panjang representasi biner dari$n$$M$$|M| < l$$M$$n$$l^2$$l = \lceil \log{n} \rceil$$n$

Jelas dalam , karena diberikan dan , hanya mensimulasikan untuk langkah dan jika berhenti membandingkan hasilnya dengan .$\mathsf{NP}$$n$$M$$M$$l^2$$n$

Makalah FOCS'17 kami pada Aritmatika Presburger Pendek adalah contoh masalah "alami" yaitu NP-c, dan menggunakan bilangan bulat konstan dalam input, katakanlah . Berbeda dengan Manders-Adleman dalam hal semua hambatannya adalah ketidaksetaraan. Lihat posting blog Gil Kalai untuk beberapa latar belakang. $C$$C< 220$

Bagaimana dengan masalah PARTISI ?