Оракульное отделение некоторых сложностных классов и нижние оценки сложности персептронов, решающих некоторые проблемы отделения

В первой части настоящей работы доказано, что относительно случайного оракула существуют бесконечные множества в NP, которые не имеют бесконечных Co-NP-подмножеств (Co-NP-иммунные NP-множества). Во второй части работы доказано, что любой персептрон, отделяющий булевы матрицы, в которых каждая строка содержит хотя бы одну единицу, от матриц, в которых многие строки (скажем, 99%) состоят из одних нулей, должен иметь большой порядок или большой общий вес. Этот результат развивает известную теорему “один в блоке” Минского и Пейперта, утверждающую, что никакой персептрон маленького порядка не может по булевской матрице выяснить, содержит ли каждая еe строка хотя бы одну единицу. В качестве следствия мы доказываем, что $\text{AM}\cap\text{Co-AM}\not\subseteq\text{PP}$ относительно некоторого оракула.
Библиография: 21 наименование.