Ist ein NP-Härtenachweis eines NP-harten Problems ein Beitrag?

18

Ich löse ein Problem, von dem behauptet wird, dass es an anderer Stelle NP-hart ist, etwa in der Zeitung [XYZ]. Die in [XYZ] angegebene NP-Härte ist kompliziert und verwendet fortschrittliche Techniken. Nach einigen Recherchen und Arbeiten ist es mir gelungen, die NP-Härte einfach und eindeutig nachzuweisen. Ich frage mich, ob dies als Beitrag angesehen wird oder nicht. Ich versuche meine Arbeit zu motivieren, habe aber keinen ähnlichen Weg gefunden.

Ich weiß nicht, ob dies der richtige Ort ist, um zu fragen, oder sollte ich zur Akademie gehen?

research-practice writing zdm
quelle
15
Das Vereinfachen von Beweisen ist ein Standardbeitrag (und manchmal nützlich). Sehen Sie nach, ob Ihr einfacher Beweis verallgemeinert wird, um etwas anderes NP-hartes zu beweisen (das war vielleicht noch nicht bekannt)
Ryan Williams
8
Wenn Ihnen die Vereinfachung wichtig genug ist, können Sie sie jederzeit aufschreiben und an arxiv senden. Wenn es andere Leute interessiert, wird es früher oder später zitiert. Im Allgemeinen kann es eine Herausforderung sein, solche vereinfachten Proof-Papiere für Konferenzen / Journale zu akzeptieren.
Sariel Har-Peled
8
Vereinfachte Beweise beinhalten / nutzen oft eine bestimmte Struktur des Problems aus, so dass Sie manchmal ein stärkeres Ergebnis in Form von "Dieses Problem ist auch im eingeschränkten Fall von ____ NP-hart" erhalten. Wenn Sie von einem anderen Problem ableiten, können weitere Eigenschaften übertragen werden, z. B. die Härte in der Approximierbarkeit oder die parametrisierte Komplexität. Suchen Sie daher nach solchen stärkeren Beobachtungen. Selbst ohne Verstärkung würde ich sagen, dass ein alternativer Beweis immer noch ein Beitrag ist, besonders wenn er vereinfacht ist, aber ich stimme zu, dass er für einige ein harter Verkauf ist.
JimN
1
Einfachere Beweise sind in einführenden oder pädagogischen Texten immer vorzuziehen. Vielleicht möchten Sie einen Übersichtsartikel oder ein Besprechungskapitel für ein anstehendes Buch über Ihre Region schreiben (wenn Sie Student sind, wissen die Vorgesetzten normalerweise über solche Aktivitäten Bescheid oder sind an solchen Aktivitäten beteiligt) und sagen: "Problem X wurde zuerst als NP-Problem erkannt. hart von Z, geben wir hier einen vereinfachten Beweis: "Auch wenn Ihr Beweis technisch nicht der stärkste in einem Parameter ist, aber viel einfacher als der formal beste Beweis, könnte Ihre Darstellung für einen Einführungstext dennoch von hoher Relevanz sein.
Martin Schwarz

Antworten:

14

Es gibt Orte, die sich für elegante Beweise vorhandener Ergebnisse interessieren, siehe zum Beispiel das Symposium zur Einfachheit von Algorithmen .

Ja, in einigen Fällen kann ein eleganter Beweis als Beitrag angesehen werden, insbesondere wenn er neue Einsichten bietet.

Gopi
quelle
-2

Hängt davon ab, welches NP-Problem schwer ist. Ein berühmter (zB 3SAT) wäre ein netter Beitrag. Ein zufälliges der 15k NP-harten Probleme wäre weniger.

user48607
quelle