Essential covers were introduced by Linial and Radhakrishnan as a model that captures two complementary properties: (1) all variables must be included and (2) no element is redundant. In their seminal paper, they proved that every essential cover of the $n$-dimensional hypercube must be of size at least $\Omega(n^{0.5})$. Later on, this notion found several applications in complexity theory. We improve the lower bound to $\Omega(n^{0.52})$, and describe two applications.
翻译:Linial 和 Radhakrishnan 将基本覆盖作为一种模型,它捕捉了两个互补属性:(1) 必须包含所有变量, (2) 任何元素都不是多余的。 在它们的重要论文中,它们证明美元-维超立方体的每一个基本覆盖必须至少大小$\Omega(n ⁇ /0.5})$。 稍后,这一概念在复杂理论中发现了一些应用。 我们把下限提高到$\Omega(n ⁇ 0.52})$, 并描述了两种应用。