Обсуждение:m-сводимость

Заголовок надо написать с маленькой буквы. Тому, кто сможет это нормально сделать, — приз. Похоже, без некоторой магии и лёгкого ковыряния в конфигах не получится. Хинт. Кирилл Елагин

А, не, смотрите-ка, заработало. Надо бы запилить, всё же, шаблончик из ссылки… Кирилл Елагин

Как обычно, закончилось тем, что я сам и запилил… Кирилл Елагин

По конспекту

У тебя на полном серьёзе два разных множества натуральных чисел? Я что-то вообще с трудом улавливаю связь между сводимостью каких-то там множеств натуральных чисел и тем, что надо получить, собственно. Кирилл Елагин

В первом абзаце доказательства всё правильно, но использована какая-то идиотская терминология («одно множество отличается от другого в точке») и вообще как-то убого написано. Это надо удалить и написать своими словами так чтобы прочитать можно было потом. Во втором абзаце вообще какая-то беда. Если не считать, что я так и не понял, что такое номер функции, вычисленной от множества, то надо, наверное, заметить, что я вообще не понял, какие номера и зачем ты вычисляешь. А теперь FATALITY: эта твоя «теорема» прямо следует из второго свойства, так что тянет максимум на следствие. Кирилл Елагин

А вот свойства надо бы доказать. Кирилл Елагин

Сейчас всё ок, но нужно добавить какой-нибудь простенький пример. Не заумные вроде сведения МПСП к ПСП, а что-нибудь самое элементарное, типа как на практике у доски решали. Кирилл Елагин