Apakah bukti kekerasan NP dari masalah NP hard dianggap sebagai kontribusi?

18

Saya memecahkan masalah yang diklaim sebagai NP-hard di tempat lain, katakan di koran [XYZ]. Kekerasan NP yang disediakan dalam [XYZ] rumit dan menggunakan teknik-teknik canggih. Setelah beberapa penelitian dan pekerjaan, saya berhasil memberikan bukti kekerasan NP yang sederhana dan jelas. Saya bertanya-tanya apakah ini dianggap sebagai kontribusi atau tidak? Saya mencoba memotivasi pekerjaan saya tetapi saya tidak menemukan jalan yang sama.

Saya tidak tahu apakah ini tempat yang tepat untuk bertanya atau haruskah saya kuliah?

research-practice writing zdm
sumber
15
Bukti penyederhanaan adalah jenis kontribusi standar (dan terkadang bermanfaat). Lihat apakah bukti sederhana Anda digeneralisasikan untuk membuktikan sesuatu yang lain NP sulit (yang mungkin belum diketahui)
Ryan Williams
8
Jika Anda cukup peduli tentang penyederhanaan, Anda selalu dapat menuliskannya, dan mempostingnya ke arxiv. Jika orang lain peduli, cepat atau lambat itu akan dikutip. Secara umum, mendapatkan makalah bukti yang disederhanakan seperti itu yang diterima di konferensi / jurnal dapat menjadi tantangan.
Sariel Har-Peled
8
Bukti sederhana sering melibatkan / mengeksploitasi struktur tertentu dalam masalah, jadi kadang-kadang Anda mendapatkan hasil yang lebih kuat dalam bentuk "masalah ini NP-keras bahkan dalam kasus terbatas ____". Jika Anda mengurangi dari masalah yang berbeda, mungkin Anda memiliki sifat lebih lanjut yang ditransfer, seperti kekerasan dalam aproksimasi atau kompleksitas parameter, jadi lihatlah jenis pengamatan yang lebih kuat ini. Bahkan tanpa penguatan apa pun, saya akan mengatakan bahwa bukti alternatif masih merupakan kontribusi, terutama jika itu disederhanakan, tetapi saya setuju bahwa itu adalah penjualan yang sulit bagi sebagian orang.
JimN
1
Bukti yang lebih sederhana selalu lebih disukai dalam teks pengantar atau pedagosial. Jadi, Anda mungkin ingin menulis artikel ulasan atau bab ulasan untuk buku yang akan datang di daerah Anda (jika Anda seorang siswa, pengawas biasanya tahu tentang atau terlibat dalam kegiatan tersebut) dan mengatakan "Masalah X pertama kali ditunjukkan sebagai NP- keras oleh Z, kami memberikan bukti yang disederhanakan di sini: "Bahkan jika bukti Anda secara teknis bukan yang terkuat dalam beberapa parameter, tetapi jauh lebih sederhana daripada bukti terbaik secara formal, eksposisi Anda mungkin masih sangat relevan untuk teks pengantar.
Martin Schwarz

Jawaban:

14

Ada tempat yang tertarik dengan bukti elegan dari hasil yang ada, lihat misalnya Simposium tentang Kesederhanaan dalam Algoritma .

Jadi ya, dalam beberapa kasus bukti elegan dapat dianggap sebagai kontribusi, terutama jika itu menawarkan wawasan baru.

Gopi
sumber
-2

Tergantung masalah NP mana yang sulit. Yang terkenal (misalnya, 3SAT) akan menjadi kontribusi yang bagus. Salah satu acak dari masalah 15k NP-hard akan kurang begitu.

pengguna48607
sumber