Pages that link to "Item:Q4210150"
From MaRDI portal
The following pages link to New Collapse Consequences of NP Having Small Circuits (Q4210150):
Displaying 20 items.
- Average-case intractability vs. worst-case intractability (Q598182) (← links)
- The shrinking property for NP and coNP (Q627189) (← links)
- Arthur and Merlin as oracles (Q649095) (← links)
- Complexity classes of equivalence problems revisited (Q716333) (← links)
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\) (Q859979) (← links)
- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly (Q1029043) (← links)
- On hard instances (Q1575555) (← links)
- Some structural properties of SAT (Q1587336) (← links)
- Reducing the number of solutions of NP functions (Q1608321) (← links)
- Competing provers yield improved Karp-Lipton collapse results (Q1775885) (← links)
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes. (Q1872705) (← links)
- Towards efficient universal planning: A randomized approach (Q1978311) (← links)
- Circuit lower bounds from learning-theoretic approaches (Q2636410) (← links)
- On the Limit of Some Algorithmic Approach to Circuit Lower Bounds (Q2944904) (← links)
- A Tight Karp-Lipton Collapse Result in Bounded Arithmetic (Q3540180) (← links)
- On Pseudodeterministic Approximation Algorithms. (Q5005164) (← links)
- Relations and equivalences between circuit lower bounds and karp-lipton theorems (Q5091782) (← links)
- (Q5121895) (← links)
- Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma (Q5130843) (← links)
- The power of natural properties as oracles (Q6116834) (← links)
