For any set of lengths , choose at length a constant-zero Boolean circuit when , and an AND of all inputs when . This uses gates. If is undecidable, so is , yet it belongs to P/poly. Since all NP languages are decidable by certificate enumeration, this proves P/poly is not equal to NP; it does not resolve containment in the other direction.
Articles by others on the same topic
There are currently no matching articles.