Изменения

Классы NP, coNP, Σ₁, Π₁

207 байт добавлено, 01:13, 25 марта 2016

→‎Свойства: Пофиксил отступы у списка

Пусть <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>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>:~~<code>~~

<tex>r(x)\colon</tex>

'''while''' <tex>cur \ne n</tex>

'''return''' ''true''

: Цикл совершит не более <~~/code~~tex>n<br/tex>итераций, т.к. на каждой итерации левая граница диапазона увеличивается как минимум на 1.

}}

130

правок