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 and dimension (Q287068) (← links)
- Sparse sets, approximable sets, and parallel queries to NP (Q294651) (← links)
- Local restrictions from the Furst-Saxe-Sipser paper (Q519884) (← links)
- The fault tolerance of NP-hard problems (Q553311) (← links)
- The strong exponential hierarchy collapses (Q584250) (← links)
- The isomorphism conjecture for constant depth reductions (Q619896) (← links)
- Separating NE from some nonuniform nondeterministic complexity classes (Q652627) (← links)
- Cook versus Karp-Levin: Separating completeness notions if NP is not small (Q671427) (← links)
- On quasilinear-time complexity theory (Q672330) (← links)
- A note on P-selective sets and closeness (Q673619) (← links)
- Relativized isomorphisms of NP-complete sets (Q687510) (← links)
- Collapsing and separating completeness notions under average-case and worst-case hypotheses (Q693053) (← links)
- The effective entropies of some extensions of context-free languages (Q751289) (← links)
- Effective entropies and data compression (Q751832) (← links)
- On the p-isomorphism conjecture (Q758202) (← links)
- Some consequences of non-uniform conditions on uniform classes (Q794427) (← links)
- Polynomial time computations in models of ET (Q795035) (← links)
- On small generators (Q802309) (← links)
- Padding, commitment and self-reducibility (Q808694) (← links)
- Generalized juntas and NP-hard sets (Q837194) (← links)
- Complexity results in graph reconstruction (Q867853) (← links)
- Comparing reductions to NP-complete sets (Q879596) (← links)
- \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP (Q908700) (← links)
- Honest polynomial time reducibilities and the \(P=?NP\) problem (Q909455) (← links)
- New developments in structural complexity theory (Q913509) (← links)
- Kolmogorov complexity and degrees of tally sets (Q916650) (← links)
- Bi-immunity results for cheatable sets (Q920981) (← links)
- Universal relations and {\#}P-completeness (Q954984) (← links)
- The complexity of unions of disjoint sets (Q955349) (← links)
- Non-mitotic sets (Q1019177) (← links)
- A low and a high hierarchy within NP (Q1052097) (← links)
- On self-reducibility and weak P-selectivity (Q1054475) (← links)
- Robust algorithms: a different approach to oracles (Q1063417) (← links)
- On some natural complete operators (Q1064780) (← links)
- On one-one polynomial time equivalence relations (Q1068536) (← links)
- Independence results about context-free languages and lower bounds (Q1071500) (← links)
- Reductions among polynomial isomorphism types (Q1077412) (← links)
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP (Q1079364) (← links)
- Continuous optimization problems and a polynomial hierarchy of real functions (Q1086557) (← links)
- NP is as easy as detecting unique solutions (Q1090454) (← links)
- On solving hard problems by polynomial-size circuits (Q1095663) (← links)
- A comparison of polynomial time completeness notions (Q1097692) (← links)
- On hardness of one-way functions (Q1097693) (← links)
- On one-way functions and polynomial-time isomorphisms (Q1097694) (← links)
- On helping by robust oracle machines (Q1097695) (← links)
- A classification of complexity core lattices (Q1099613) (← links)
- On simple and creative sets in NP (Q1099614) (← links)
- Can the catenation of two weakly sparse languages be dense? (Q1102760) (← links)
- The complexity of optimization problems (Q1107309) (← links)
- Isomorphisms and 1-L reductions (Q1107310) (← links)
