Pages that link to "Item:Q3978778"
From MaRDI portal
The following pages link to Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets (Q3978778):
Displaying 46 items.
- NP-hard sets are superterse unless NP is small (Q290182) (← links)
- Sparse sets, approximable sets, and parallel queries to NP (Q294651) (← links)
- The complexity of manipulative attacks in nearly single-peaked electorates (Q490458) (← links)
- The fault tolerance of NP-hard problems (Q553311) (← links)
- Separating NE from some nonuniform nondeterministic complexity classes (Q652627) (← links)
- Cook versus Karp-Levin: Separating completeness notions if NP is not small (Q671427) (← links)
- A note on P-selective sets and closeness (Q673619) (← links)
- Autoreducibility, mitoticity, and immunity (Q881593) (← links)
- On the asymmetric complexity of the group-intersection problem (Q963437) (← links)
- On polynomial time one-truth-table reducibility to a sparse set (Q1191028) (← links)
- On sparse hard sets for counting classes (Q1210293) (← links)
- Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets (Q1276171) (← links)
- Sparse hard sets for P: Resolution of a conjecture of Hartmanis (Q1288202) (← links)
- On reductions of NP sets to sparse sets (Q1329162) (← links)
- Space-efficient recognition of sparse self-reducible languages (Q1337147) (← links)
- Geometric sets of low information content (Q1351460) (← links)
- Quasi-linear truth-table reductions to \(p\)-selective sets (Q1351469) (← links)
- Resolution of Hartmanis' conjecture for NL-hard sparse sets (Q1575434) (← links)
- Some structural properties of SAT (Q1587336) (← 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)
- Nonuniform lowness and strong nonuniform lowness (Q1894328) (← links)
- Reductions between disjoint NP-pairs (Q2387199) (← 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)
- Sparse parameterized problems (Q2564046) (← links)
- The Birth and Early Years of Parameterized Complexity (Q2908529) (← links)
- Introduction to Autoreducibility and Mitoticity (Q2973718) (← links)
- Self-reducible sets of small density (Q3210176) (← links)
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets (Q3210177) (← links)
- The Fault Tolerance of NP-Hard Problems (Q3618596) (← links)
- (Q3811710) (← links)
- On lower bounds of the closeness between complexity classes (Q4032931) (← links)
- (Q4256649) (← links)
- An observation on probability versus randomness with applications to complexity classes (Q4298369) (← links)
- (Q4373559) (← links)
- On sets bounded truth-table reducible to $P$-selective sets (Q4717049) (← links)
- Monotonous and randomized reductions to sparse sets (Q4717050) (← links)
- (Q4814348) (← links)
- Upper bounds for the complexity of sparse and tally descriptions (Q4864446) (← links)
- On sets bounded truth-table reducible to P-selective sets (Q4942650) (← links)
- On complexity classes and algorithmically random languages (Q5096791) (← links)
- Reductions to sets of low information content (Q5204315) (← links)
- Separating NE from Some Nonuniform Nondeterministic Complexity Classes (Q5323096) (← links)
- (Q5875468) (← links)
- Splitting NP-complete sets infinitely (Q6551699) (← links)
