130
правок
Изменения
→Определение: return жирным
q(x):
y = <tex>\{0,1\}^{p(|x|)}</tex>
'''return ''' R(x,y)
Если <tex>x\in L</tex>, то программа сможет «угадать» подходящий сертификат. Если <tex>x\notin L</tex>, то подходящего сертификата не существует по определению. Таким образом, <tex>q</tex> разрешает <tex>L</tex>, следовательно <tex>L\in \mathrm{NP}</tex>.
*<tex>\mathrm{NP} \subset \mathrm{\Sigma_1}</tex>.
