A prova de dureza NP de um problema NP-duro é considerada uma contribuição?

18

Estou resolvendo um problema que é considerado difícil em NP em outros lugares, digamos no artigo [XYZ]. A dureza NP fornecida em [XYZ] é complicada e utiliza técnicas avançadas. Após algumas pesquisas e trabalhos, consegui dar uma prova simples e clara da dureza do NP. Gostaria de saber se isso é considerado uma contribuição ou não? Estou tentando motivar meu trabalho, mas não encontrei um caminho semelhante.

Não sei se este é o lugar certo para perguntar ou devo ir para a academia?

research-practice writing zdm
fonte
15
Simplificar provas é um tipo de contribuição padrão (e às vezes útil). Veja se seus generaliza prova simples para provar outra coisa NP hard (que talvez não estivesse já conhecida)
Ryan Williams
8
Se você se importa o suficiente com a simplificação, sempre pode anotá-la e publicá-la no arxiv. Se outras pessoas se importarem, mais cedo ou mais tarde isso será citado. De um modo geral, a aceitação de documentos de provas simplificados aceitos em conferências / revistas pode ser desafiadora.
Sariel Har-Peled
8
As provas simplificadas geralmente envolvem / exploram uma certa estrutura no problema; portanto, às vezes, você obtém um resultado mais forte na forma de "esse problema é difícil para o NP, mesmo no caso restrito de ____". Se você estiver reduzindo de um problema diferente, pode ser que você tenha outras propriedades transferidas, como dureza na aproximação ou complexidade parametrizada, portanto, procure esse tipo de observação mais forte. Mesmo sem qualquer fortalecimento, eu diria que uma prova alternativa ainda é uma contribuição, especialmente se for simplificada, mas concordo que é uma venda difícil para alguns.
21918 JimNa segunda
1
As provas mais simples são sempre preferíveis em textos introdutórios ou pedagógicos. Portanto, você pode escrever um artigo de revisão ou um capítulo de revisão para um próximo livro em sua área (se você é um estudante, os supervisores geralmente conhecem ou estão envolvidos em tais atividades) e dizem "Primeiro, o problema X mostrou ser NP- por Z, oferecemos uma prova simplificada aqui: "Mesmo que sua prova não seja tecnicamente a mais forte em algum parâmetro, mas muito mais simples que a melhor prova formalmente, sua exposição ainda pode ser altamente relevante para um texto introdutório.
Martin Schwarz

Respostas:

14

Existem locais interessados ​​em provas elegantes de resultados existentes, veja, por exemplo, o Simpósio sobre Simplicidade em Algoritmos .

Portanto, sim, em alguns casos, uma prova elegante pode ser considerada uma contribuição, especialmente se oferecer novas idéias.

Gopi
fonte
-2

Depende de qual problema difícil do NP. Um famoso (por exemplo, 3SAT) seria uma boa contribuição. Um problema aleatório de 15k NP-difícil seria menos.

user48607
fonte