Pages that link to "Item:Q671427"
From MaRDI portal
The following pages link to Cook versus Karp-Levin: Separating completeness notions if NP is not small (Q671427):
Displaying 20 items.
- NP-hard sets are superterse unless NP is small (Q290182) (← links)
- A thirty year old conjecture about promise problems (Q347124) (← links)
- A note on measuring in P (Q596092) (← links)
- The size of SPP (Q596117) (← links)
- Collapsing and separating completeness notions under average-case and worst-case hypotheses (Q693053) (← links)
- Comparing reductions to NP-complete sets (Q879596) (← links)
- Martingale families and dimension in P (Q930913) (← links)
- Genericity and measure for exponential time (Q1350990) (← links)
- An excursion to the Kolmogorov random strings (Q1362331) (← links)
- Complete distributional problems, hard languages, and resource-bounded measure (Q1575682) (← links)
- Autoreducibility of NP-complete sets under strong hypotheses (Q1745961) (← links)
- Bi-immunity separates strong NP-completeness notions (Q1887166) (← links)
- Hard sets are hard to find (Q1961379) (← links)
- Nondeterminisic sublinear time has measure 0 in P (Q1999993) (← links)
- Nonuniform reductions and NP-completeness (Q2158296) (← links)
- Polylog depth, highness and lowness for E (Q2304528) (← links)
- Reductions between disjoint NP-pairs (Q2387199) (← links)
- Upward separations and weaker hypotheses in resource-bounded measure (Q2465636) (← links)
- Partial bi-immunity, scaled dimension, and NP-completeness (Q2480744) (← links)
- Equivalence of measures of complexity classes (Q5048952) (← links)
