Pages that link to "Item:Q2475580"
From MaRDI portal
The following pages link to If NP languages are hard on the worst-case, then it is easy to find their hard instances (Q2475580):
Displaying 10 items.
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (Q301524) (← links)
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification (Q744610) (← links)
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification (Q3088109) (← links)
- Circuit lower bounds from NP-hardness of MCSP under turing reductions (Q5092477) (← links)
- A remark on pseudo proof systems and hard instances of the satisfiability problem (Q5109236) (← links)
- Hard Instances of Algorithms and Proof Systems (Q5892128) (← links)
- (Q6084353) (← links)
- Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? (Q6113106) (← links)
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) (Q6140986) (← links)
- Constructive separations and their consequences (Q6566463) (← links)
