Pages that link to "Item:Q1168733"

The following pages link to Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis (Q1168733):

Displaying 38 items.

• On vanishing of Kronecker coefficients (Q1686840) (← links)
• On sparseness, reducibilities, and complexity (Q1779309) (← links)
• Core instances for testing: a case study (Q1779532) (← links)
• Relativizing relativized computations (Q1822968) (← links)
• On inefficient special cases of NP-complete problems (Q1823688) (← links)
• Tally NP sets and easy census functions. (Q1854340) (← links)
• Nonuniform lowness and strong nonuniform lowness (Q1894328) (← links)
• Taming the knight's tour: minimizing turns and crossings (Q2067620) (← links)
• Computational complexity of synchronization under sparse regular constraints (Q2140506) (← links)
• Small polyomino packing (Q2361496) (← links)
• A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly (Q2366689) (← links)
• Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity (Q2373445) (← links)
• The complexity of minimum difference cover (Q2458927) (← links)
• Sparse parameterized problems (Q2564046) (← links)
• Self-reducibility (Q2639637) (← links)
• On the complexity of the spaced seeds (Q2643726) (← links)
• On intractability of the classUP (Q3201755) (← 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 Power of Self-Reducibility: Selectivity, Information, and Approximation (Q3297822) (← links)
• Classifying the computational complexity of problems (Q3781088) (← links)
• On Upward Drawings of Trees on a Given Grid (Q4625120) (← links)
• Complexity classes between $\Theta _k^P$ and $\Delta _k^P$ (Q4717047) (← 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)
• A refinement of the low and high hierarchies (Q4841766) (← links)
• Upper bounds for the complexity of sparse and tally descriptions (Q4864446) (← links)
• On sparseness and Turing reducibility over the reals (Q4916198) (← links)
• Structural complexity theory: Recent surprises (Q5056087) (← links)
• On the power of parity polynomial time (Q5096157) (← links)
• Reductions to sets of low information content (Q5204315) (← links)
• Separating NE from Some Nonuniform Nondeterministic Complexity Classes (Q5323096) (← links)
• Weak cardinality theorems (Q5718691) (← links)
• On the power of parity polynomial time (Q5750401) (← links)
• (Q5875468) (← links)
• Special issue: 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Seattle, WA, USA, June 1--3, 1998 (Q5929910) (← links)
• The complexity of grid coloring (Q6109067) (← links)