Rambler's Top100 Service
Поиск   
 
Обратите внимание!   BOAI: наука должна быть открытой Обратите внимание!
 
  Наука >> Математика >> Математическое образование | Популярные статьи
 Написать комментарий  Добавить новое сообщение
Next: 4.2. Класс Up: 4. Как различать сложные Previous: 4. Как различать сложные Contents: Содержание

4.1. Полиномиальная сводимость

Определение 4.   Сводимость по Карпу. Функция $f_1$ сводится к функции $f_2$ (обозначение $f_1\propto f_2$), если существует такая функция $f\relax \in\P $, что $\forall  x\:
f_1(x)=f_2(f(x))$.

Сводимость по Карпу также называют полиномиальной сводимостью, а часто - просто сводимостью. Отношение $\propto$ будем рассматривать как формальный вариант отношения "задача $f_1$ не сложнее задачи $f_2$". Действительно, если $f_2\in \P $, то и $f_1\in\P $: полиномиальный алгоритм для вычисления $f_1$ использует последовательно полиномиальные алгоритмы для $f$ (на входе $x$) и для $f_2$ (на входе $f(x)$).




Написать комментарий
 Copyright © 2000-2015, РОО "Мир Науки и Культуры". ISSN 1684-9876 Rambler's Top100 Яндекс цитирования