В чем сущность полиномиальных преобразований?

Question

[Денис Каракчиев]

Возможно 2 последних тега лишние, я просто не совсем сориентировался. Задачи P и NP классов связаны с теорией алгоритмов. Но при попытке найти что-то о полиномиальных преобразованиях, я вижу только связанное с географией.

Суть: я готовлюсь к поступлению в магистратуру (сдаче экзамена) по направлению "Математика и компьютерные науки". Это к тому, что география здесь слабо вяжется. Заранее спасибо за ответы.

Comments

[B@rmaley.e><e]

Думаю, Вы ищете "полиномиальные сведения".

[Moskus]

Еще вспоминаются преобразования Чирнгаузена (которого все преподы почему-то зовут "Чирнгауз").

Answer 1

[Dvvarreyn]

полиномиальных преобразований
Это похоже на перевод с русского на английский и обратно.
Полиномиальная сводимость, реже трансформируемость, сводимость по Карпу, иногда просто сводимость.
По-английски polynomial-time reduction, очень редко transformation.

Кратко, суть в том, что две задачи полиномиально сводимы, если существует полиномиальное преобразование одной в другую. В классе P (NP) есть задачи, к которым сводятся все остальные задачи из класса.

Comments

[Денис Каракчиев]

на счет перевода - это формулировка, данная в вузе =) Кстати, правильно ли я понимаю, что полином суть то же, что и многочлен?

[Dvvarreyn]

Да, полином и многочлен - это одно и тоже.

[Денис Каракчиев]

Dvvarreyn: если не затруднит, не могли бы Вы привести пример подобных преобразований (если они существуют, я так и не разобрался)?

[Денис Каракчиев]

Dvvarreyn: также Вы написали "...полиномально сводимы, если существует полиномиальное преобразование..." так что же все-таки это самое преобразование есть? =)

[Dvvarreyn]

Денис Каракчиев: Я тоже когда учил не понимал. Там в учебниках всякие сложные примеры: сводимости задачи о клике к задаче о выполнимости. Какие-то языки. Машины Тьюринга.
Всё по сути проще некуда.
Пусть есть задача сложить два числа. Это задача решается за линейное число операций от длины максимального из чисел (ну то есть, если делать руками как в первом классе, то max(N_1, N_2) + 1, ну а у машины Тьюринга будет там ещё некоторая мультипликативная константа, так как она туда сюда будет бегать, на Марковских алгоритмах вроде бы можно без беготни, но это всё детали) .

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

Этот пример не совсем корректен в том плане, что настоящая сложность умножения ~ n log(n)*log(log(n)) , а когда говорят о сложности класса задач, говорят о минимальной сложности по всем возможным алгоритмам. Но в целом идея сводимости ровно в этом — один класс задач решаем через другой.

А дальше эту простую вещь всякие сумасшедшие люди формализовали (от слова «формалин»).
И вам нужно теперь понять, что описание задачи — это некоторый язык. Ну то есть, чтобы задать вход в машину Тьюринга для произвольных двух числе вам нужно некоторое систематической описание этой задачи. Это описание и есть язык.
Две задачи — два языка. Постановка - слово на языке. Один язык сводится к другому (один класс задач к другому), если на той же МТ можно написать программу преобразующую любое слово (постановку) на одном языке в некоторое слово (постановку) на другом.
Если существует программа на МТ, такая что это преобразование требует полиномиальное число операций от длины входа (слова, постановки), то сводимость полиномиальная.

Для экзамена вам вероятно нужно разораться с тем, с чего я начал — сводимостью клики (или другой NP задачи) к 3-выполнимости. Что это за задачи, почему 3-выполнимость NP, как через неё записываются другие задачи. Все эти задачи будут задачами распознования, то есть в них ответ бинарный («да» или «нет»). Понимать, что такое МТ и НМТ.

[Денис Каракчиев]

Dvvarreyn: лучшие слова, которые можно услышать от незнакомого человека в 3 часа ночи. Спасибо, вроде что-то начал понимать =) под НМТ Вы имеете ввиду недетерменированную МТ?

[Dvvarreyn]

Денис Каракчиев:

под НМТ Вы имеете ввиду недетерменированную МТ?

да.