论文标题
测试过滤器甲骨模型中的理想性
Testing idealness in the filter oracle model
论文作者
论文摘要
杂物的过滤器Oracle由有限的集合$ V $以及Oracle组成，鉴于任何集合$ x \ subseteq v $，在单位时间内决定是否包含杂物的成员。令$ \ mathfrak {a} _ {2n} $是一种算法，给定任何混乱$ \ mathcal {c} $通过$ 2N $元素通过过滤器oracle决定是否决定是否理想。我们证明，在最坏的情况下，$ \ mathfrak {a} _ {2n} $必须至少对过滤器Oracle进行$ 2^n $调用。我们的证明使用了立方体的理论。
A filter oracle for a clutter consists of a finite set $V$ along with an oracle which, given any set $X\subseteq V$, decides in unit time whether or not $X$ contains a member of the clutter. Let $\mathfrak{A}_{2n}$ be an algorithm that, given any clutter $\mathcal{C}$ over $2n$ elements via a filter oracle, decides whether or not $\mathcal{C}$ is ideal. We prove that in the worst case, $\mathfrak{A}_{2n}$ must make at least $2^n$ calls to the filter oracle. Our proof uses the theory of cuboids.
