Abstract:
In the first part of the paper we prove that, relative to a random oracle, the class NP contains infinite sets having no infinite Co-NP-subsets (Co-NP-immune sets). In the second part we prove that perceptrons separating Boolean matrices in which each row contains at least one 1 from matrices in which many rows (say 99% of them) have no 1's must have either large size or large order. This result partially strengthens the “one-in-a-box” theorem of Minsky and
Papert [16] which states that perceptrons of small order cannot decide if every row of a given Boolean matrix has a 1. As a corollary, we prove that
$\text{AM}\cap\text{Co-AM}\not\subseteq\text{PP}$ under some oracles.
Fulltext:
PDF file (3753 kB)
