Liste des problèmes fortement NP-difficiles avec des données numériques

11

Je recherche des problèmes fortement NP-durs pour une réduction. Jusqu'à présent, j'ai trouvé les problèmes suivants:

Problème de 3 partitions
problème de bin-packing
Correspondance numérique tridimensionnelle
TSP
Tout problème NP-complet sans données numériques, par exemple, SATISFACILITÉ, CYCLE HAMILTONIEN, 3-COLORABILITÉ.

Quelqu'un connaît-il une liste de problèmes fortement NP-difficiles?

Sinon, construisons-en un ici. Connaissez-vous d'autres problèmes avec les données numériques qui sont fortement NP-difficiles?

Je suis particulièrement intéressé par les problèmes fortement NP-difficiles sur les graphiques pondérés.

np-hardness big-list hamiltonian-paths sigal maon
la source

5

Rendez votre question autonome en définissant «fortement».

Tyson Williams

3

Le chemin le plus long est une généralisation du chemin hamiltonien, il est donc fortement NP-difficile.

Michael Lampis

(1) Est-ce que «fortement NP» est une faute de frappe pour «fortement NP-dur»? (2) Je ne pense pas que «nous pouvons en faire un ici».

Tsuyoshi Ito

la coloration de l'arc-en-ciel semble être difficile par rapport à la largeur de l'arbre, peut-être aussi fortement NP difficile ...

vzn

3

Voici un problème fortement complet $NP$ (avec des données numériques comme vous l'avez demandé):

Problème de Schur Triples :

Entrée: liste de 3N entiers positifs distincts

Question: Y a-t-il une partition de la liste en N triplets telle que pour chaque triple ? $(a_i, b_i, c_i)$ $a_i + b_i= c_i$ $i$

La condition que tous les nombres doivent être distincts rend le problème très intéressant et McDiarmid l'appelle étonnamment gênant .

Mohammad Al-Turkistany
la source

0

En réfléchissant aux réponses possibles, j'ai trouvé ce simple problème numérique fortement NP-complet:

PRODUIT SOUS-ENSEMBLE SANS CARRÉ: Étant donné entiers, trouvez d'entre eux dont le produit est sans carré. $3N$ $N$

Esquisse de preuve: à partir d'une instance Exact Cover by 3 sets (X3C) (fortement NPC), étiquetez chaque élément de l'univers avec un nombre premier distinct (vous pouvez en générer en temps polynomial); puis convertissez chaque triple des sous-ensembles en . $3|X|$ $(x,y,z)$ $xyz$

Je ne l'ai trouvé nulle part, donc ça peut être quelque peu "original".

Il ressemble évidemment au PRODUIT SOUS-ENSEMBLE mieux connu (qui n'est pas fortement NPC en raison de la présence du produit cible , voir David S. Johnson: The NP-Completeness Column: An Ongoing Guide. 393-405). $B$

Il peut également être piraté un peu pour obtenir d'autres variantes, comme:

Étant donné entiers, trouvez d'entre eux dont le produit est une puissance parfaite ; $3N$ $N$ $21$
Étant donné nombres entiers, trouvez un sous-ensemble dont le produit est le 3N-ème primitif. (sorte de tricherie :-) $N$

Marzio De Biasi
la source

@domotorp: J'ai supprimé la question; je copie / colle ici votre commentaire sur la transformation de la contrainte en "... trouvez un sous-ensemble dont le produit est un nombre libre carré supérieur à M ...": "Tout d'abord, considérez que vous multipliez chaque nombre par un nombre premier différent, très grand, de sorte que tous ceux-ci ont à peu près la même taille. Ensuite, sélectionner N nombres équivaudrait à obtenir un grand produit. Nous ne pouvons pas (encore) générer de grands nombres premiers en P, mais en fait nous n'avons pas besoin eux - au lieu de chaque nombre premier, nous pouvons utiliser des nombres premiers sans carré relatifs et ceux que nous pouvons générer en calculant les premiers nombres premiers polynomialement nombreux

Marzio De Biasi

0

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

Mohammad Al-Turkistany
la source

0

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

$NP$ $3$

J'espère que cela t'aides!

PageWizard
la source

Liste des problèmes fortement NP-difficiles avec des données numériques

Réponses: