Pages that link to "Item:Q4128010"
From MaRDI portal
The following pages link to On Isomorphisms and Density of $NP$ and Other Complete Sets (Q4128010):
Displaying 50 items.
- Complexity classes without machines: on complete languages for UP (Q1109566) (← links)
- Collapsing degrees (Q1109766) (← links)
- Graph isomorphism is in the low hierarchy (Q1116696) (← links)
- Notes on polynomial levelability (Q1119389) (← links)
- Discrete extremal problems (Q1152306) (← links)
- On the structure of sets in NP and other complexity classes (Q1162811) (← links)
- A note on natural complete sets and Goedel numberings (Q1163015) (← links)
- A note on sparse oracles for NP (Q1164997) (← links)
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis (Q1168733) (← links)
- On sparse sets in NP-P (Q1172386) (← links)
- An appraisal of computational complexity for operations researchers (Q1173532) (← links)
- On sets polynomially enumerable by iteration (Q1176233) (← links)
- On p-creative sets and p-completely creative sets (Q1183565) (← links)
- Nonuniform complexity and the randomness of certain complete languages (Q1184988) (← links)
- Oracles for structural properties: The isomorphism problem and public-key cryptography (Q1190988) (← links)
- Logarithmic advice classes (Q1193903) (← links)
- Polynomial-time compression (Q1198955) (← links)
- Circuit size relative to pseudorandom oracles (Q1208410) (← links)
- On sparse hard sets for counting classes (Q1210293) (← links)
- On polynomial time isomorphisms of some new complete sets (Q1245571) (← links)
- On log-tape isomorphisms of complete sets (Q1249940) (← links)
- Exponential-time and subexponential-time sets (Q1261474) (← links)
- Probabilistic complexity classes and lowness (Q1263979) (← links)
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem (Q1276160) (← links)
- Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets (Q1276171) (← links)
- Sparse hard sets for P: Resolution of a conjecture of Hartmanis (Q1288202) (← links)
- The relative power of logspace and polynomial time reductions (Q1312179) (← links)
- Quasi-injective reductions (Q1314394) (← links)
- One-way functions and the isomorphism conjecture (Q1329733) (← links)
- The random oracle hypothesis is false (Q1333397) (← links)
- Space-efficient recognition of sparse self-reducible languages (Q1337147) (← links)
- Locating \(P\)/poly optimally in the extended low hierarchy (Q1341715) (← links)
- Computation times of NP sets of different densities (Q1348523) (← links)
- Almost every set in exponential time is P-bi-immune (Q1349712) (← links)
- Scalability and the isomorphism problem (Q1351582) (← links)
- DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization (Q1362330) (← links)
- An excursion to the Kolmogorov random strings (Q1362331) (← links)
- The isomorphism conjecture holds and one-way functions exist relative to an oracle (Q1362333) (← links)
- On P-immunity of exponential time complete sets (Q1362336) (← links)
- Index sets and presentations of complexity classes (Q1366536) (← links)
- No NP problems averaging over ranking of distributions are harder (Q1391309) (← links)
- An oracle builder's toolkit (Q1398366) (← links)
- Inverting onto functions. (Q1426007) (← links)
- Resolution of Hartmanis' conjecture for NL-hard sparse sets (Q1575434) (← links)
- On hard instances (Q1575555) (← links)
- On vanishing of Kronecker coefficients (Q1686840) (← links)
- Sparse selfreducible sets and nonuniform lower bounds (Q1755786) (← links)
- On sparseness, reducibilities, and complexity (Q1779309) (← links)
- Core instances for testing: a case study (Q1779532) (← links)
- Some consequences of the existnce of pseudorandom generators (Q1822961) (← links)
