Some consequences of non-uniform conditions on uniform classes (Q794427): Difference between revisions

Non-uniform complexity classes appear from the circuit complexity. It is proved that if non-uniform classes \(\Sigma_ i/poly=\Pi_ i/poly,\) then \(\Sigma_{i+2}=\Pi_{i+2}\) in the Meyer-Stockmeyer hierarchy. Apart that, some connections between coincidence of complexity classes and sparse complete sets are ascertained. If there exists a sparse set which is complete for co-NP relatively to conjunctive reducibility then \(P=NP\). Besides that, if NP is conjunctively and disjunctively reducible to a sparse NP-complete set then also \(P=NP\).