Une preuve de dureté NP d'un problème NP-dur est-elle considérée comme une contribution?

18

Je résout un problème qui est censé être NP-difficile ailleurs, disons dans l'article [XYZ]. La dureté NP fournie dans [XYZ] est compliquée et utilise des techniques avancées. Après quelques recherches et travaux, j'ai réussi à donner une preuve simple et claire de la dureté NP. Je me demande si cela est considéré comme une contribution ou non? J'essaie de motiver mon travail mais je n'ai pas trouvé de chemin similaire.

Je ne sais pas si c'est le bon endroit pour demander ou dois-je aller au milieu universitaire?

research-practice writing zdm
la source
15
La simplification des preuves est un type de contribution standard (et parfois utile). Voyez si votre simple preuve se généralise pour prouver quelque chose d'autre NP difficile (qui n'était peut-être pas déjà connu)
Ryan Williams
8
Si vous vous souciez suffisamment de la simplification, vous pouvez toujours l'écrire et la publier sur arxiv. Si d'autres personnes s'en soucient, tôt ou tard, cela sera cité. De manière générale, l'obtention de ces preuves simplifiées acceptées dans des conférences / revues peut être difficile.
Sariel Har-Peled
8
Les preuves simplifiées impliquent / exploitent souvent une certaine structure dans le problème, donc parfois vous obtenez un résultat plus fort sous la forme de "ce problème est NP-difficile même dans le cas restreint de ____". Si vous réduisez d'un problème différent, il se peut que vous ayez d'autres propriétés à transférer, telles que la dureté dans l'approximation ou la complexité paramétrée, alors recherchez ce type d'observations plus fortes. Même sans aucun renforcement, je dirais qu'une preuve alternative est toujours une contribution, surtout si elle est simplifiée, mais je conviens que c'est difficile à vendre pour certains.
JimN
1
Des preuves plus simples sont toujours préférables dans les textes d'introduction ou pédagogiques. Donc, vous voudrez peut-être écrire un article de revue ou un chapitre de revue pour un livre à venir sur votre région (si vous êtes un étudiant, les superviseurs connaissent ou sont impliqués dans de telles activités) et disent "Le problème X a d'abord été montré comme NP- difficile par Z, nous donnons ici une preuve simplifiée: "Même si votre preuve n'est pas techniquement la plus solide dans certains paramètres, mais beaucoup plus simple que la meilleure preuve formelle, votre exposition pourrait toujours être très pertinente pour un texte d'introduction.
Martin Schwarz

Réponses:

14

Il y a des lieux qui sont intéressés par des preuves élégantes de résultats existants, voir par exemple le Symposium sur la simplicité dans les algorithmes .

Alors oui, dans certains cas, une preuve élégante peut être considérée comme une contribution, surtout si elle offre de nouvelles perspectives.

Gopi
la source
-2

Dépend de quel problème difficile NP. Un célèbre (par exemple, 3SAT) serait une belle contribution. Un problème aléatoire parmi les 15k NP-durs le serait moins.

user48607
la source