Pages that link to "Item:Q1223166"
From MaRDI portal
The following pages link to A comparison of polynomial time reducibilities (Q1223166):
Displaying 50 items.
- Optimization problems and the polynomial hierarchy (Q1152218) (← links)
- Complexity of graph embeddability problems (Q1152224) (← links)
- Discrete extremal problems (Q1152306) (← links)
- Some observations on NP real numbers and P-selective sets (Q1164623) (← links)
- A note on sparse oracles for NP (Q1164997) (← links)
- Reductions on NP and p-selective sets (Q1166515) (← links)
- On truth-table reducibility to SAT (Q1173957) (← links)
- On polynomial time one-truth-table reducibility to a sparse set (Q1191028) (← links)
- The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory (Q1193873) (← links)
- On sparse hard sets for counting classes (Q1210293) (← links)
- Complexity-class-encoding sets (Q1237360) (← links)
- Log space machines with multiple oracle tapes (Q1242686) (← links)
- On languages specified by relative acceptance (Q1249438) (← links)
- Complexity in mechanized hypothesis formation (Q1256867) (← links)
- Hard promise problems and nonuniform complexity (Q1261468) (← links)
- On 1-truth-table-hard languages (Q1261477) (← links)
- Strong nondeterministic Turing reduction - a technique for proving intractability (Q1262762) (← links)
- The relative power of logspace and polynomial time reductions (Q1312179) (← links)
- Space-efficient recognition of sparse self-reducible languages (Q1337147) (← links)
- The structure of the honest polynomial m-degrees (Q1341316) (← links)
- Locating \(P\)/poly optimally in the extended low hierarchy (Q1341715) (← links)
- Genericity and measure for exponential time (Q1350990) (← links)
- Geometric sets of low information content (Q1351460) (← links)
- Quasi-linear truth-table reductions to \(p\)-selective sets (Q1351469) (← links)
- Universally serializable computation (Q1384538) (← links)
- P-immune sets with holes lack self-reducibility properties. (Q1401340) (← links)
- Query complexity of membership comparable sets. (Q1401341) (← links)
- A second step towards complexity-theoretic analogs of Rice's Theorem (Q1575716) (← links)
- Recursion-theoretic ranking and compression (Q1713478) (← links)
- Autoreducibility of NP-complete sets under strong hypotheses (Q1745961) (← links)
- On the reducibility of sets inside NP to sets with low information content (Q1765294) (← links)
- Complexity of the calculus of continued fraction representation of real numbers (Q1814099) (← links)
- The price of universality (Q1815426) (← links)
- Distinguishing conjunctive and disjunctive reducibilities by sparse sets (Q1823690) (← links)
- On the complexity of data disjunctions. (Q1853503) (← links)
- Optimal series-parallel trade-offs for reducing a function to its own graph (Q1854508) (← links)
- Degrees of Dowd-type generic oracles (Q1854543) (← links)
- Uniformly hard languages. (Q1874273) (← links)
- Bi-immunity separates strong NP-completeness notions (Q1887166) (← links)
- Non-uniform reductions (Q1959376) (← links)
- The complexity of online bribery in sequential elections (Q2121471) (← links)
- Complexity-theoretic aspects of expanding cellular automata (Q2278565) (← links)
- A complexity theory for feasible closure properties (Q2366687) (← links)
- Query-monotonic Turing reductions (Q2383592) (← links)
- Bounded truth table does not reduce the one-query tautologies to a random oracle (Q2388434) (← links)
- Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey (Q2436695) (← links)
- Partial bi-immunity, scaled dimension, and NP-completeness (Q2480744) (← links)
- Error-bounded probabilistic computations between MA and AM (Q2507698) (← links)
- Sets without subsets of higher many-one degree (Q2565991) (← links)
- Polynomial-time reducibilities and ``almost all'' oracle sets (Q2639849) (← links)
