109
правок
Изменения
→Доказательство: часть доказательства
==Доказательство==
<math>L=\left\{\varphi | \varphi \in SAT \and f(|\varphi|) \text{ is even}\right\}</math>
<math>A=\left\{x | f(|x|) \text{ is even}\right\}</math>
<math>f(0) = f(1) = 0</math>
Определим <math>f(n)</math>:
*'''Случай 1:''' <math>f(n-1)=2i</math>.
*: Если существует <math>x</math>, такой что <math>|x| < \log_2n</math> и <math>M_i(x) \ne L(x)</math>, то <math>f(n) = f(n-1)+1</math>, иначе <math>f(n) = f(n-1)</math>
*'''Случай 2:''' <math>f(n-1)=2i+1</math>.
*:Если существует <math>x</math>, такой что <math>|x| < \log_2n</math> и <math>SAT(x) \ne L(g_i(x))</math>, то <math>f(n) = f(n-1)+1</math>, иначе <math>f(n) = f(n-1)</math>
