Pages that link to "Item:Q1166515"
From MaRDI portal
The following pages link to Reductions on NP and p-selective sets (Q1166515):
Displaying 49 items.
- Cook versus Karp-Levin: Separating completeness notions if NP is not small (Q671427) (← links)
- Reducibility classes of P-selective sets (Q672155) (← links)
- Some results on selectivity and self-reducibility (Q672402) (← links)
- P-selectivity: Intersections and indices (Q673115) (← links)
- Choosing, agreeing, and eliminating in communication complexity (Q744609) (← links)
- Cook reducibility is faster than Karp reducibility in NP (Q751812) (← links)
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes (Q809600) (← links)
- On the complexity of kings (Q846367) (← links)
- A note on degrees of presentation of games as relational structures (Q912772) (← links)
- Robust machines accept easy sets (Q914369) (← links)
- Non-mitotic sets (Q1019177) (← links)
- On self-reducibility and weak P-selectivity (Q1054475) (← links)
- Strong nondeterministic polynomial-time reducibilities (Q1055405) (← links)
- Promise problems complete for complexity classes (Q1109568) (← links)
- Positive relativizations of the \(P=?\) NP problem (Q1124342) (← links)
- Some observations on NP real numbers and P-selective sets (Q1164623) (← links)
- An NL hierarchy (Q1182111) (← links)
- Hard promise problems and nonuniform complexity (Q1261468) (← links)
- Probabilistic complexity classes and lowness (Q1263979) (← links)
- On symmetric differences of NP-hard sets with weakly P-selective sets (Q1314375) (← links)
- Quasi-linear truth-table reductions to \(p\)-selective sets (Q1351469) (← links)
- P-immune sets with holes lack self-reducibility properties. (Q1401340) (← links)
- Query complexity of membership comparable sets. (Q1401341) (← links)
- On the computational complexity of best Chebyshev approximations (Q1821775) (← links)
- Bi-immunity separates strong NP-completeness notions (Q1887166) (← links)
- On membership comparable sets (Q1961377) (← links)
- The complexity of online bribery in sequential elections (Q2121471) (← links)
- A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly (Q2366689) (← links)
- Reductions between disjoint NP-pairs (Q2387199) (← links)
- Partial bi-immunity, scaled dimension, and NP-completeness (Q2480744) (← links)
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets (Q3210177) (← links)
- The Power of Self-Reducibility: Selectivity, Information, and Approximation (Q3297822) (← links)
- The Complexity of Reasoning for Fragments of Default Logic (Q3637157) (← links)
- Characterizations of reduction classes modulo oracle conditions (Q3763590) (← links)
- Generalized theorems on relationships among reducibility notions to certain complexity classes (Q4298368) (← links)
- Fault-tolerance and complexity (Extended abstract) (Q4630260) (← links)
- On sets bounded truth-table reducible to $P$-selective sets (Q4717049) (← links)
- Monotonous and randomized reductions to sparse sets (Q4717050) (← links)
- Complete sets and closeness to complexity classes (Q4727430) (← links)
- On closure properties of bounded two-sided error complexity classes (Q4835865) (← links)
- (Q5018515) (← links)
- On monotonous oracle machines (Q5096350) (← links)
- Promise problems and access to unambiguous computation (Q5096827) (← links)
- SELF-SPECIFYING MACHINES (Q5249003) (← links)
- Non-mitotic Sets (Q5458830) (← 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)
- Dot operators (Q5958134) (← links)
- Polynomial-time axioms of choice and polynomial-time cardinality (Q6109071) (← links)
