摘要：Given N instances (X_1,t_1),â¦,(X_N,t_N) of Subset Sum, the AND Subset Sum problem asks to determine whether all of these instances are yes-instances; that is, whether each set of integers X_i has a subset that sums up to the target integer t_i. We prove that this problem cannot be solved in time OÌf((N â<. t_max)^{1-ε}), for t_max = max_i t_i and any ε > 0, assuming the â^ â^f Strong Exponential Time Hypothesis (â^â^f-SETH). We then use this result to exclude OÌf(n+P_maxâ<.n^{1-ε})-time algorithms for several scheduling problems on n jobs with maximum processing time P_max, assuming â^â^f-SETH. These include classical problems such as 1 â^' w_jU_j, the problem of minimizing the total weight of tardy jobs on a single machine, and Pâ,, â^' U_j, the problem of minimizing the number of tardy jobs on two identical parallel machines.
关键词：SETH; fine grained complexity; Subset Sum; scheduling
