Pages that link to "Item:Q1054475"
From MaRDI portal
The following pages link to On self-reducibility and weak P-selectivity (Q1054475):
Displaying 49 items.
- AND-compression of NP-complete problems: streamlined proof and minor observations (Q309801) (← links)
- Is Valiant-Vazirani's isolation probability improvable? (Q354652) (← links)
- The consequences of eliminating NP solutions (Q458458) (← links)
- Reducibility classes of P-selective sets (Q672155) (← links)
- Some results on selectivity and self-reducibility (Q672402) (← links)
- Optimal advice (Q672755) (← links)
- P-selectivity: Intersections and indices (Q673115) (← links)
- A note on P-selective sets and closeness (Q673619) (← links)
- On sets Turing reducible to p-selective sets (Q675861) (← links)
- Complexity classes of equivalence problems revisited (Q716333) (← links)
- Choosing, agreeing, and eliminating in communication complexity (Q744609) (← links)
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes (Q809600) (← links)
- On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P (Q845727) (← links)
- A result relating disjunctive self-reducibility to P-immunity (Q915447) (← links)
- The Boolean hierarchy of NP-partitions (Q924719) (← links)
- On problems without polynomial kernels (Q1034099) (← links)
- Continuous optimization problems and a polynomial hierarchy of real functions (Q1086557) (← links)
- On helping by robust oracle machines (Q1097695) (← links)
- Promise problems complete for complexity classes (Q1109568) (← links)
- On polynomial-time Turing and many-one completeness in PSPACE (Q1193869) (← links)
- Logarithmic advice classes (Q1193903) (← links)
- Hard promise problems and nonuniform complexity (Q1261468) (← links)
- A hierarchy based on output multiplicity (Q1274991) (← links)
- On symmetric differences of NP-hard sets with weakly P-selective sets (Q1314375) (← links)
- Geometric sets of low information content (Q1351460) (← links)
- Quasi-linear truth-table reductions to \(p\)-selective sets (Q1351469) (← links)
- Time bounded frequency computations (Q1383147) (← links)
- Query complexity of membership comparable sets. (Q1401341) (← links)
- Some connections between bounded query classes and non-uniform complexity. (Q1426008) (← links)
- Reducing the number of solutions of NP functions (Q1608321) (← links)
- Sparse selfreducible sets and nonuniform lower bounds (Q1755786) (← links)
- On the reducibility of sets inside NP to sets with low information content (Q1765294) (← links)
- Competing provers yield improved Karp-Lipton collapse results (Q1775885) (← links)
- On membership comparable sets (Q1961377) (← links)
- A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly (Q2366689) (← links)
- One query reducibilities between partial information classes (Q2575741) (← links)
- Self-reducibility (Q2639637) (← links)
- Self-reducible sets of small density (Q3210176) (← links)
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets (Q3210177) (← links)
- In Memoriam: Ker-I Ko (1950–2018) (Q3297820) (← links)
- The Power of Self-Reducibility: Selectivity, Information, and Approximation (Q3297822) (← links)
- New collapse consequences of NP having small circuits (Q4645178) (← links)
- On sets bounded truth-table reducible to $P$-selective sets (Q4717049) (← links)
- Monotonous and randomized reductions to sparse sets (Q4717050) (← links)
- Upper bounds for the complexity of sparse and tally descriptions (Q4864446) (← links)
- Derandomizing Isolation in Space-Bounded Settings (Q5232318) (← links)
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses (Q5501928) (← links)
- ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES (Q5704373) (← links)
- The communication complexity of enumeration, elimination, and selection (Q5956009) (← links)
