Надо ли приводить доказательство теорем в автореферате?

[Варвара]

Есть в моей диссертации одна теорема. Она, конечно, нужная, но не основная. Доказательство в меру тривиальное, но довольно объемное.

Вопрос про то, что делать с ней в автореферате? Нужно ли приводить это доказательство целиком, или можно просто описать принцип парой предложений? Или убрать доказательство совсем?

[Riper]

целиком точно не надо. но то что она доказана вами в рамках диссертации упомянуть надо.

[osmos]

Вопрос про то, что делать с ней в автореферате? Нужно ли приводить это доказательство целиком, или можно просто описать принцип парой предложений? Или убрать доказательство совсем? Если это теорема, доказанная Вами лично, тем более она является ключевой в работе, тогда надо. А если просто общеизвестная (или не очень известная) теорема, тогда можно и не приводить ее доказательство, а просто указать, кем она была доказана, в каких работах и т.д.

[Варвара]

osmos, это моя теорема, мною доказанная, но ее доказательство является техническим, известным приемом для доказательства аналогичных теорем. Теорема о том, что поставленная мной задача является NP-трудной. Она не является ключевой в диссертации, ключевая - модель для решения задачи. Но теорема важная... Вот. :)

[Riper]

Теорема о том, что поставленная мной задача является NP-трудной. Она не является ключевой в диссертации, ключевая - модель для решения задачи. Но теорема важная... Вот. :)
Я бы написал формулировку, а потом что-то в духе "теорема доказана в рамках диссертации методом приведения поставленной задачи к NP-трудной задачи о (подставить наименование задачи к которой приводили)"

[osmos]

Но теорема важная Тогда кратко приведите ее доказательство.

Добавлено через 5 минут 16 секунд
Я бы написал формулировку Если кратко никак не получается ее доказать, тогда коротко напишите, что за теорема и каким методом (способом, приемом...) ее доказывают. можете в одном предложении описать суть метода - коротко и выдержанно. Тем более, если это общеизвестный прием.
Также сделайте ссылку что-то типа "процедура решения приводится в соответствующей литературе по теории алгоритмов".

[Варвара]

Riper, в том-то и проблема, что я не сводила задачу, а через машины Тьюринга доказывала. В итоге там два листа формул почти без текста. В стиле: а вот этот кусок МТ соответствует вот такому куску моей модели. Короче это доказательство сделать нереально, потому что оно и в диссертации уже максимально краткое. Метод названия не имеет, и книжку с его описанием найти никак не могу (видела только в учебниках, а ссылаться на учебники не разрешает научрук)... Эх... Буду пытаться сформулировать одним предложением...

Спасибо за советы!

[osmos]

Метод названия не имеет Тогда посмотрите в учебниках, что там пишут. А на 2 стр. в автореферате не надо ничего доказывать. А вот фразу "процедура решения..." приведите. Не указывайте конкретную литературу, так и пишите "в соответствующей литературе". Кому приспичит и надо будет - те найдут сами, не дети. Удачи!

[Riper]

Метод названия не имеет, и книжку с его описанием найти никак не могу (видела только в учебниках, а ссылаться на учебники не разрешает научрук)... Эх... Буду пытаться сформулировать одним предложением...

Ну а какая разница?
вместо:
"теорема доказана в рамках диссертации методом приведения поставленной задачи к NP-трудной задачи о (подставить наименование задачи к которой приводили)"
пишем:
"теорема доказана в рамках диссертации методом приведения поставленной задачи к недетерминированной машине Тьюринга работающей на такой-то ленте за такое-то время"

книжек полно на эту тему.
Я бы для начала посмотрел: Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи (в интернете полно мест где можно скачать в формате djvu) -- скорее всего там должно быть.

[Варвара]

Riper, примерно так и написала в итоге.

Книжек-то полно, но конкретно этот способ я только в учебниках видела, а в монографиях - нет. В Гэри-Джонсоне по-другому написано (я ее для начала посмотрела... еще два года назад :)). Не могу именно такой способ найти в литературе. Ладно, напишу, что из Гэри-Джонсона, там похоже. Но всё равно не так.

[Riper]

Riper, примерно так и написала в итоге.

Подумалось: а Вы доказываете что нельзя привести к ДМТ?

[Варвара]

Я доказываю как эквивалентность МТ и моей модели. Только начало формулирую по-другому, потому что мне эта эквивалентность не нужна, мне NP-трудность нужна. То есть говорю, что вот, сведем любую NP-полную задачу к нашей. NP-полная задача алгоритмически разрешима, значит, существует решающая ее МТ. И перевожу эту МТ в объекты моей модели, фактически, моделирую МТ в своих терминах. А в конце говорю, что так как мы взяли произвольную NP-полную и свели ее к нашей задаче, значит, наша задача NP-трудная. Вот так как-то! :)

[Olafson]

Если жанр теоремы в Ваших палестинах редкий -- можете щегольнуть. Если теоремы не редкость -- не досаждайте общественности. Хороша или нет теорема -- специалисты поймут по формулировке. Если невмоготу хороша -- заинтересуются, да еще и отзыв напишут:)

Постскриптум. У меня в работе примерно десяток теорем -- а похвастаться ничем не могу!:)