109
правок
Изменения
→Иллюстрация: исправлено еще немного ошибок
к этому то, что проверку на принадлежность <math>f(\varphi)</math>
<math>SAT \cap A</math> можно осуществить за <math>O(2^{poly})</math>
(это следует из её принадлежности классу <math>NP</math>), получаем программу,
разрешающую <math>\varphi</math> за полином. Утверждение о том, что все формулы
<math>\varphi</math> длиной <math>^{2k+1}10</math> принадлежат классу
<math>P</math> , скорее всего не верно, и ,следовательно, язык
<math>SAT \cap A</math> не является NP-полным.
