Daftar masalah NP-hard sangat dengan data numerik

Saya mencari masalah NP-hard sangat untuk pengurangan. Sejauh ini saya telah menemukan masalah berikut:

• Masalah 3-partisi
• masalah bin-packing
• Pencocokan numerik 3 dimensi
• TSP
• Setiap masalah NP-lengkap tanpa data numerik, misalnya, KEPUASAN, SIKLUS HAMILTONIAN, 3-KOLABURITAS.

Apakah ada yang tahu daftar masalah NP-hard sangat?

Jika tidak, mari kita membangun satu di sini. Apakah Anda tahu masalah lain dengan data numerik yang sangat NP-keras?

Saya sangat tertarik pada masalah NP-hard pada grafik tertimbang.

Berikut ini adalah sangat -Lengkap$NP$ masalah (dengan data numerik seperti yang Anda minta):

Masalah Schur Triples :

Input: daftar 3N yang berbeda bilangan bulat positif

Pertanyaan: Apakah ada partisi dari daftar ke N Triple sehingga a i + b i = c i untuk setiap tiga i ?$(a_i, b_i, c_i)$$a_i + b_i= c_i$$i$

Kondisi bahwa semua angka harus berbeda membuat masalahnya sangat menarik dan McDiarmid menyebutnya sangat menyusahkan .

Sambil memikirkan kemungkinan jawaban saya datang dengan masalah sederhana yang sangat lengkap dengan angka NP ini:

$3N$$N$

$3|X|$$(x,y,z)$$xyz$

Saya tidak menemukannya di mana pun, jadi itu bisa agak "asli".

$B$

Itu juga dapat diretas sedikit untuk mendapatkan varian lain, seperti:

• $3N$$N$$21$
• $N$

$k= \Omega(n)$$NP$

$NP$$P||C_{max}$

$NP$$3$

Semoga ini membantu!