We prove that (i) either there is a language in E requiring exponential circuit complexity, or (ii) the class NP is not closed under the complementation, or (iii) there is no p-optimal propositional proof system.
We prove that (i) either there is a language in E requiring exponential circuit complexity, or (ii) the class NP is not closed under the complementation, or (iii) there is no p-optimal propositional proof system. (en)
Dokážeme, že buď existuje jazyk v E mající exponenciální obvodovou složitost, či třída NP není uzavřena na doplněk, či neexistuje p-optimální důkazový systém. (cs)