Lista de problemas fortemente NP-difíceis com dados numéricos

Eu estou procurando problemas fortemente difíceis de NP para uma redução. Até agora, encontrei os seguintes problemas:

• Problema de 3 partições
• problema de embalagem
• Correspondência tridimensional numérica
• TSP
• Qualquer problema de NP completo sem dados numéricos, por exemplo, SATISFIABILIDADE, CICLO HAMILTONIANO, 3-COLOURABILITY.

Alguém sabe de uma lista de problemas fortemente NP-difíceis?

Caso contrário, vamos construir um aqui. Você conhece outros problemas com dados numéricos fortemente NP-hard?

Estou particularmente interessado em problemas fortemente difíceis de NP em gráficos ponderados.

$NP$

Schur triplica o problema :

Entrada: lista de 3N números inteiros positivos distintos

$(a_i, b_i, c_i)$$a_i + b_i= c_i$$i$

A condição de que todos os números devem ser distintos torna o problema muito interessante e McDiarmid o chama de surpreendentemente problemático .

Ao pensar em possíveis respostas, eu vim com esse problema simples numérico fortemente NP-completo:

$3N$$N$

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

Não o encontrei em lugar nenhum, portanto pode ser um pouco "original".

$B$

Também pode ser hackeado um pouco para obter outras variantes, como:

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

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

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

$NP$$3$

Espero que isto ajude!