The following pages link to On sparse sets in NP-P (Q1172386):
Displayed 23 items.
- On the polynomial IO-complexity (Q582102) (← links)
- Average-case intractability vs. worst-case intractability (Q598182) (← links)
- A note on P-selective sets and closeness (Q673619) (← links)
- On random reductions from sparse sets to tally sets (Q685530) (← links)
- A result relating disjunctive self-reducibility to P-immunity (Q915447) (← links)
- On the complexity of test case generation for NP-hard problems (Q917311) (← links)
- On one-one polynomial time equivalence relations (Q1068536) (← links)
- Strong and robustly strong polynomial-time reducibilities to sparse sets (Q1177170) (← links)
- Logarithmic advice classes (Q1193903) (← links)
- A positive relativization of polynomial time versus polylog space (Q1261484) (← links)
- Locating \(P\)/poly optimally in the extended low hierarchy (Q1341715) (← links)
- Computation times of NP sets of different densities (Q1348523) (← links)
- On resource-bounded instance complexity (Q1351945) (← links)
- On the computational structure of the connected components of a hard problem (Q1607000) (← links)
- On the reducibility of sets inside NP to sets with low information content (Q1765294) (← links)
- Distinguishing conjunctive and disjunctive reducibilities by sparse sets (Q1823690) (← links)
- Tally NP sets and easy census functions. (Q1854340) (← links)
- Sparse sets and collapse of complexity classes (Q1854459) (← links)
- NL-printable sets and nondeterministic Kolmogorov complexity (Q2369009) (← links)
- On intractability of the classUP (Q3201755) (← links)
- Limitations of the upward separation technique (Q3490941) (← links)
- Towards the Actual Relationship Between NP and Exponential Time (Q4238424) (← links)
- NL-printable sets and Nondeterministic Kolmogorov Complexity (Q4924524) (← links)