¿Una prueba de dureza NP de un problema NP-duro se considera una contribución?

18

Estoy resolviendo un problema que se afirma que es NP-hard en otro lugar, digamos en el artículo [XYZ]. La dureza NP proporcionada en [XYZ] es complicada y utiliza técnicas avanzadas. Después de un poco de investigación y trabajo, logré dar una prueba simple y clara de la dureza NP. Me pregunto si esto se considera como una contribución o no. Estoy tratando de motivar mi trabajo pero no encontré un camino similar.

No sé si este es el lugar correcto para preguntar o si debo ir a la academia.

research-practice writing zdm
fuente
15
Simplificar las pruebas es un tipo de contribución estándar (y a veces útil). Vea si su simple prueba generaliza para probar algo más NP difícil (que tal vez no se sabía)
Ryan Williams
8
Si le importa lo suficiente la simplificación, siempre puede escribirla y publicarla en el arxiv. Si a otras personas les importa, tarde o temprano sería citado. En términos generales, obtener pruebas de pruebas simplificadas aceptadas en conferencias / revistas puede ser un desafío.
Sariel Har-Peled
8
Las pruebas simplificadas a menudo involucran / explotan una determinada estructura en el problema, por lo que a veces se obtiene un resultado más fuerte en la forma de "este problema es NP-difícil incluso en el caso restringido de ____". Si está reduciendo debido a un problema diferente, puede ser que tenga más propiedades de transferencia, como la dureza de la aproximación o la complejidad parametrizada, así que busque este tipo de observaciones más fuertes. Incluso sin ningún fortalecimiento, diría que una prueba alternativa sigue siendo una contribución, especialmente si se simplifica, pero estoy de acuerdo en que es difícil de vender para algunos.
JimN
1
Las pruebas más simples siempre son preferibles en textos introductorios o pedagógicos. Por lo tanto, es posible que desee escribir un artículo de revisión o un capítulo de revisión para un próximo libro en su área (si es estudiante, los supervisores generalmente conocen o están involucrados en tales actividades) y dicen "El problema X se mostró primero como NP- Por Z, damos una prueba simplificada aquí: "Incluso si su prueba no es técnicamente la más fuerte en algún parámetro, pero es mucho más simple que la prueba formalmente mejor, su exposición podría ser muy relevante para un texto introductorio.
Martin Schwarz

Respuestas:

14

Hay lugares que están interesados ​​en pruebas elegantes de resultados existentes, ver por ejemplo el Simposio sobre simplicidad en algoritmos .

Entonces, sí, en algunos casos una prueba elegante puede considerarse como una contribución, especialmente si ofrece nuevas ideas.

Gopi
fuente
-2

Depende del problema NP difícil. Una famosa (por ejemplo, 3SAT) sería una buena contribución. Uno aleatorio de los 15k problemas NP-hard sería menos.

usuario48607
fuente