Czy dowód twardości NP na problem związany z twardością NP uważa się za wkład?

18

Rozwiązuję problem, który w innym miejscu jest trudny do NP, powiedzmy w artykule [XYZ]. Twardość NP podana w [XYZ] jest skomplikowana i wykorzystuje zaawansowane techniki. Po kilku badaniach i pracach udało mi się dać prosty i jasny dowód na twardość NP. Zastanawiam się, czy jest to uważane za wkład, czy nie? Próbuję motywować swoją pracę, ale nie znalazłem podobnej ścieżki.

Nie wiem, czy jest to właściwe miejsce, aby zapytać, czy powinienem pójść na naukę?

research-practice writing zdm
źródło
15
Uproszczenie dowodów to standardowy (a czasem użyteczny) rodzaj wkładu. Sprawdź, czy Twój prosty dowód uogólnia, aby udowodnić coś innego NP trudny (co być może nie było jeszcze znane)
Ryan Williams
8
Jeśli dbasz o uproszczenie, zawsze możesz to po prostu zapisać i opublikować w arxiv. Jeśli inni się tym przejmują, wcześniej czy później zostanie to zacytowane. Mówiąc ogólnie, uzyskanie takich uproszczonych dokumentów potwierdzających przyjętych na konferencje / czasopisma może być trudne.
Sariel Har-Peled,
8
Uproszczone dowody często obejmują / wykorzystują określoną strukturę problemu, więc czasami uzyskuje się silniejszy wynik w postaci „ten problem jest trudny do przeprowadzenia nawet w ograniczonym przypadku ____”. Jeśli redukujesz z innego problemu, być może masz inne właściwości przenoszenia, takie jak twardość w przybliżeniu lub sparametryzowana złożoność, więc szukaj tego rodzaju silniejszych obserwacji. Nawet bez wzmocnienia powiedziałbym, że alternatywny dowód jest nadal wkładem, szczególnie jeśli jest uproszczony, ale zgadzam się, że dla niektórych jest to trudna sprzedaż.
JimN
1
Prostsze dowody są zawsze preferowane w tekstach wprowadzających lub pedagocialnych. Możesz więc napisać artykuł z recenzją lub rozdział z recenzją dla nadchodzącej książki na twoim obszarze (jeśli jesteś studentem, przełożeni zwykle wiedzą o takich działaniach lub są w nie zaangażowani) i powiedzą: „Problem X po raz pierwszy okazał się NP- ciężko przez Z, dajemy tutaj uproszczony dowód: „Nawet jeśli pod względem technicznym twój dowód nie jest najsilniejszy w jakimś parametrze, ale znacznie prostszy niż formalnie najlepszy dowód, twoja ekspozycja może nadal być bardzo istotna dla tekstu wprowadzającego.
Martin Schwarz

Odpowiedzi:

14

Istnieją miejsca, które są zainteresowane eleganckimi dowodami istniejących wyników, patrz na przykład Sympozjum na temat prostoty w algorytmach .

Tak więc, w niektórych przypadkach elegancki dowód można uznać za wkład, szczególnie jeśli oferuje on nowe informacje.

Gopi
źródło
-2

Zależy, który NP trudny problem. Słynny (np. 3SAT) byłby dobrym wkładem. Przypadkowy jeden z 15k trudnych problemów NP byłby mniejszy.

użytkownik48607
źródło