130
правок
Изменения
→Свойства: ехало полиномиальное время через полиномиальное время, видит полиномиальное время: в полиномиальное время полиномиальное
Пусть <tex>p</tex> разрешает <tex>L_1</tex>, а <tex>q</tex> разрешает <tex>L_2</tex>.
:1. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cap L_2</tex>за полиномиальное время:
<tex>r(x)\colon</tex>
'''return''' <tex>p(x)</tex> '''and''' <tex>q(x)</tex>
:2. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex>за полиномиальное время:
<tex>r(x)\colon</tex>
'''return''' <tex>p(x)</tex> '''or''' <tex>q(x)</tex>
:3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>за полиномиальное время:
<tex>r(x)\colon</tex>
<tex>n = |x|</tex>
<tex>mid \gets?\ \{1 \mathinner{\ldotp\ldotp} n\}</tex>
'''return''' <tex>p(x[1 \mathinner{\ldotp\ldotp} mid])</tex> '''and''' <tex>q(x[mid+1 \mathinner{\ldotp\ldotp} n])</tex>
:4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex>за полиномиальное время:
<tex>r(x)\colon</tex>
<tex>n = |x|</tex>
