Pages that link to "Item:Q4305356"
From MaRDI portal
The following pages link to Measure, Stochasticity, and the Density of Hard Languages (Q4305356):
Displaying 19 items.
- NP-hard sets are superterse unless NP is small (Q290182) (← links)
- A note on measuring in P (Q596092) (← links)
- The size of SPP (Q596117) (← links)
- Dimension, halfspaces, and the density of hard sets (Q649114) (← links)
- Cook versus Karp-Levin: Separating completeness notions if NP is not small (Q671427) (← links)
- Comparing nontriviality for E and EXP (Q693048) (← links)
- Collapsing and separating completeness notions under average-case and worst-case hypotheses (Q693053) (← links)
- Genericity and randomness over feasible probability measures (Q1275002) (← links)
- Genericity and measure for exponential time (Q1350990) (← links)
- Resource bounded randomness and weakly complete problems (Q1392022) (← links)
- The zero-one law holds for BPP (Q1575726) (← links)
- Some structural properties of SAT (Q1587336) (← links)
- MAX3SAT is exponentially hard to approximate if NP has positive dimension. (Q1853564) (← links)
- Weakly complete problems are not rare (Q1918951) (← links)
- Hard sets are hard to find (Q1961379) (← links)
- Weak completeness notions for exponential time (Q2322715) (← links)
- Upward separations and weaker hypotheses in resource-bounded measure (Q2465636) (← links)
- Axiomatizing Resource Bounds for Measure (Q3091445) (← links)
- Equivalence of measures of complexity classes (Q5048952) (← links)
