论文标题
不同的矢量问题的双重指数下限
A Double Exponential Lower Bound for the Distinct Vectors Problem
论文作者
论文摘要
在（二进制）不同的矢量问题中，我们给了一个二进制矩阵A，具有成对的行不同行，并希望在最多k列中选择，以便将矩阵限制为这些列，所有行仍然是成对的。 Froese等人的结果。 [JCSS]暗示A 2^2^（o（k）） * poly（| a |） - 时间的蛮力算法，用于不同的矢量。我们表明，通过证明存在常数C，使算法求解不同的向量的存在与运行时间2^（O（2^（ck））） * Poly（| a |）的存在与指数时间假设相矛盾。
In the (binary) Distinct Vectors problem we are given a binary matrix A with pairwise different rows and want to select at most k columns such that, restricting the matrix to these columns, all rows are still pairwise different. A result by Froese et al. [JCSS] implies a 2^2^(O(k)) * poly(|A|)-time brute-force algorithm for Distinct Vectors. We show that this running time bound is essentially optimal by showing that there is a constant c such that the existence of an algorithm solving Distinct Vectors with running time 2^(O(2^(ck))) * poly(|A|) would contradict the Exponential Time Hypothesis.
