Pages that link to "Item:Q1223166"
From MaRDI portal
The following pages link to A comparison of polynomial time reducibilities (Q1223166):
Displaying 50 items.
- The complexity of computing minimal unidirectional covering sets (Q372959) (← links)
- Nontriviality for exponential time w.r.t. weak reducibilities (Q391074) (← links)
- A survey on the structure of approximation classes (Q458503) (← links)
- The complexity of manipulative attacks in nearly single-peaked electorates (Q490458) (← links)
- The fault tolerance of NP-hard problems (Q553311) (← links)
- Survey of polynomial transformations between NP-complete problems (Q555184) (← links)
- The strong exponential hierarchy collapses (Q584250) (← links)
- Cook versus Karp-Levin: Separating completeness notions if NP is not small (Q671427) (← links)
- Reducibility classes of P-selective sets (Q672155) (← links)
- Computing functions with parallel queries to NP (Q673784) (← links)
- Collapsing and separating completeness notions under average-case and worst-case hypotheses (Q693053) (← links)
- Lower bounds and the hardness of counting properties (Q703531) (← links)
- Cook reducibility is faster than Karp reducibility in NP (Q751812) (← links)
- Some consequences of non-uniform conditions on uniform classes (Q794427) (← links)
- Reducibilities on real numbers (Q795039) (← links)
- Probabilistic Turing machines and recursively enumerable Dedekind cuts (Q802546) (← links)
- On adaptive versus nonadaptive bounded query machines (Q808242) (← links)
- The complexity of Kemeny elections (Q817813) (← 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)
- Kolmogorov complexity and degrees of tally sets (Q916650) (← links)
- Bi-immunity results for cheatable sets (Q920981) (← links)
- Does truth-table of linear norm reduce the one-query tautologies to a random oracle? (Q948913) (← links)
- The complexity of unions of disjoint sets (Q955349) (← links)
- On the autoreducibility of functions (Q970103) (← links)
- Non-mitotic sets (Q1019177) (← links)
- Anyone but him: the complexity of precluding an alternative (Q1028907) (← links)
- The computational complexity of ideal semantics (Q1045987) (← links)
- A note on a theorem by Ladner (Q1051633) (← links)
- A low and a high hierarchy within NP (Q1052097) (← links)
- On self-reducibility and weak P-selectivity (Q1054475) (← links)
- Strong nondeterministic polynomial-time reducibilities (Q1055405) (← links)
- The recursion-theoretic structure of complexity classes (Q1064320) (← links)
- Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets (Q1075319) (← links)
- On the continued fraction representation of computable real numbers (Q1096627) (← links)
- A note on complete problems for complexity classes (Q1097029) (← links)
- A comparison of polynomial time completeness notions (Q1097692) (← links)
- Geometric optimization and the polynomial hierarchy (Q1102110) (← links)
- Polynomial terse sets (Q1104077) (← links)
- Geometric optimization and \(D^ P\)-completeness (Q1106665) (← links)
- More complicated questions about maxima and minima, and some closures of NP (Q1107524) (← links)
- Diagonalizations over polynomial time computable sets (Q1107526) (← links)
- Decompositions of nondeterministic reductions (Q1108263) (← links)
- Promise problems complete for complexity classes (Q1109568) (← links)
- Collapsing degrees (Q1109766) (← links)
- The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\) (Q1118407) (← links)
- A new complete language for DSPACE(log n) (Q1123607) (← links)
- Positive relativizations of the \(P=?\) NP problem (Q1124342) (← links)
- Indexings of subrecursive classes (Q1140080) (← links)
- On gamma-reducibility versus polynomial time many-one reducibility (Q1149766) (← links)
