Pages that link to "Item:Q4190619"
From MaRDI portal
The following pages link to P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP (Q4190619):
Displaying 50 items.
- NP-hard sets are superterse unless NP is small (Q290182) (← links)
- Is Valiant-Vazirani's isolation probability improvable? (Q354652) (← links)
- The shrinking property for NP and coNP (Q627189) (← links)
- Cook versus Karp-Levin: Separating completeness notions if NP is not small (Q671427) (← links)
- Reducibility classes of P-selective sets (Q672155) (← links)
- On quasilinear-time complexity theory (Q672330) (← 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)
- Choosing, agreeing, and eliminating in communication complexity (Q744609) (← links)
- Cook reducibility is faster than Karp reducibility in NP (Q751812) (← links)
- Padding, commitment and self-reducibility (Q808694) (← links)
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes (Q809600) (← links)
- On the complexity of kings (Q846367) (← links)
- Robust machines accept easy sets (Q914369) (← links)
- The complexity of unions of disjoint sets (Q955349) (← links)
- Non-mitotic sets (Q1019177) (← links)
- On self-reducibility and weak P-selectivity (Q1054475) (← links)
- A note on complete problems for complexity classes (Q1097029) (← links)
- Diagonalizations over polynomial time computable sets (Q1107526) (← links)
- Promise problems complete for complexity classes (Q1109568) (← links)
- On the relative complexity of hard problems for complexity classes without complete problems (Q1112017) (← links)
- A uniform approach to obtain diagonal sets in complexity classes (Q1164414) (← links)
- Some observations on NP real numbers and P-selective sets (Q1164623) (← links)
- Reductions on NP and p-selective sets (Q1166515) (← links)
- Hard promise problems and nonuniform complexity (Q1261468) (← links)
- A hierarchy based on output multiplicity (Q1274991) (← links)
- Boolean operations, joins, and the extended low hierarchy (Q1275091) (← links)
- Locating \(P\)/poly optimally in the extended low hierarchy (Q1341715) (← links)
- Quasi-linear truth-table reductions to \(p\)-selective sets (Q1351469) (← links)
- On resource-bounded instance complexity (Q1351945) (← links)
- Time bounded frequency computations (Q1383147) (← links)
- Query complexity of membership comparable sets. (Q1401341) (← 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)
- Optimal series-parallel trade-offs for reducing a function to its own graph (Q1854508) (← links)
- On membership comparable sets (Q1961377) (← links)
- Closure and nonclosure properties of the classes of compressible and rankable sets (Q2037201) (← links)
- A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly (Q2366689) (← links)
- Robustness of PSPACE-complete sets (Q2379952) (← links)
- Query-monotonic Turing reductions (Q2383592) (← links)
- Reductions between disjoint NP-pairs (Q2387199) (← links)
- One query reducibilities between partial information classes (Q2575741) (← links)
- Resource bounded immunity and simplicity (Q2576870) (← links)
- Fixed-parameter decidability: Extending parameterized complexity analysis (Q2958220) (← links)
- The Power of Self-Reducibility: Selectivity, Information, and Approximation (Q3297822) (← links)
- The Shrinking Property for NP and coNP (Q3507436) (← links)
- Fault-tolerance and complexity (Extended abstract) (Q4630260) (← links)
