141
правка
Изменения
м
→Свойства класса P: Замена жаргонизма
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время <tex>f(n)</tex> и использующий оракул языка <tex>A</tex>.
Пусть <tex>q</tex> {{---}} разрешитель <tex>A</tex>, работающий за полиномиальное время <tex>g(n)</tex>.
Представим себе разрешитель <tex>L</tex>, работающий как <tex>p</tex>, но использующий <tex>q</tex> вместо оракула <tex>A</tex>. Его время работы ограничено сверху значением <tex>f(n) + \sum\limits_{i=1}^{f(n)} g(f(n)) = f(n) + f(n) g(f(n))</tex>, что является полиномом (обращений к <tex>q</tex> максимум <tex>f(n)</tex>; на вход для <tex>q</tex> можем подать максимум <tex>f(n)</tex> данных, так как больше сгенерить сгенерировать бы не успели). Значит, <tex>L \in \mathrm{P}</tex>.
}}
