Считается ли доказательство NP-твердости NP-трудной задачи вкладом?

18

Я решаю проблему, которая, как утверждают, является труднопроходимой в других местах, например, в статье [XYZ]. NP-твердость, представленная в [XYZ], сложна и использует передовые методы. После некоторых исследований и работ мне удалось дать простое и ясное доказательство твердости NP. Мне интересно, если это рассматривается как вклад или нет? Я пытаюсь мотивировать свою работу, но я не нашел подобного пути.

Я не знаю, если это правильное место, чтобы спросить, или я должен идти в академию?

research-practice writing ZDM
источник
15
Упрощение доказательств является стандартным (а иногда и полезным) видом вклада. Посмотрите, обобщает ли ваше простое доказательство доказательство чего-то еще NP трудного (что, возможно, еще не было известно)
Райан Уильямс
8
Если вам небезразлично упрощение, вы всегда можете просто записать его и отправить в архив. Если другие люди заботятся, рано или поздно это будет процитировано. Вообще говоря, получение таких упрощенных корректурных работ, принятых на конференции / журналы, может быть сложной задачей.
Сариэль Хар-Пелед
8
Упрощенные доказательства часто вовлекают / используют определенную структуру в задаче, поэтому иногда вы получаете более сильный результат в виде «эта проблема NP-трудна даже в ограниченном случае ____». Если вы переходите от другой проблемы, возможно, у вас есть дополнительные свойства, такие как твердость в приближаемости или параметризованная сложность, так что ищите такие более сильные наблюдения. Даже без какого-либо усиления, я бы сказал, что альтернативное доказательство по-прежнему является вкладом, особенно если оно упрощено, но я согласен, что для некоторых это трудно продать.
ДжимН
1
Более простые доказательства всегда предпочтительнее во вводных или педагогических текстах. Поэтому вы можете написать обзорную статью или обзорную главу для будущей книги по вашему региону (если вы студент, руководители обычно знают о таких мероприятиях или участвуют в них) и сказать: «Сначала была показана проблема X - NP- В случае с Z мы приводим здесь упрощенное доказательство: «Даже если ваше доказательство технически не является самым сильным по какому-либо параметру, но намного проще, чем формально лучшее доказательство, ваше изложение может все еще иметь большое значение для вводного текста.
Мартин Шварц,

Ответы:

14

Есть места, которые интересуются изящными доказательствами существующих результатов, см., Например, Симпозиум по Простоте в Алгоритмах .

Так что да, в некоторых случаях элегантное доказательство можно рассматривать как вклад, особенно если оно предлагает новые идеи.

Гопи
источник
-2

Зависит от того, с какой NP трудная проблема. Знаменитый (например, 3SAT) был бы хорошим вкладом. Случайная из 15 000 NP-сложных проблем была бы меньше.

user48607
источник