Изменения
→Следствия
}}
==СледствияСледствие==
{{ Утверждение
| statement = Если существует решение вопроса равенства <tex>\mathrm{P}</tex> и <tex> \mathrm{NP}</tex>, то оно не должно "релятивизоваться". Поэтому стандартные техники, например диагонализация, не применимы для доказательства данного равенства.
}}
Для доказательства строгого включения классов часто используется метод диагонализации. Однако утверждения полученные при помощи данной техники могут быть "релятивизованы". То есть при "разрешении" машине Тьюринга доступа к оракулу некоторого языка доказанное соотношение классов сохраняется. Однако соотношение <tex>\mathrm{P}</tex> и <tex>\mathrm{NP}</tex> не должно "релятивизоваться" по теореме Бейкера-Гилла-Соловэя, следовательно, метод диагонализации не применим для решения этого вопроса.
[[Категория: Теория сложности]]
