Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

SETH-based Lower Bounds for Subset Sum and Bicriteria Path

SETH-based Lower Bounds for Subset Sum and Bicriteria Path Subset Sumand k-SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexity. An important open problem in this area is to base the hardness of one of these problems on the other.Our main result is a tight reduction from k-SAT to Subset Sum on dense instances, proving that Bellman’s 1962 pseudo-polynomial O*(T)-time algorithm for Subset Sum on n numbers and target T cannot be improved to time T1-ε · 2o(n) for any ε > 0, unless the Strong Exponential Time Hypothesis (SETH) fails.As a corollary, we prove a “Direct-OR” theorem for Subset Sum under SETH, offering a new tool for proving conditional lower bounds: It is now possible to assume that deciding whether one out of N given instances of Subset Sum is a YES instance requires time (N T)1-o(1). As an application of this corollary, we prove a tight SETH-based lower bound for the classical Bicriteria s,t-Path problem, which is extensively studied in Operations Research. We separate its complexity from that of Subset Sum: On graphs with m edges and edge lengths bounded by L, we show that the O(Lm) pseudo-polynomial time algorithm by Joksch from 1966 cannot be improved to Õ(L + m), in contrast to a recent improvement for Subset Sum (Bringmann, SODA 2017). http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

SETH-based Lower Bounds for Subset Sum and Bicriteria Path

Download PDF
22 pages

Loading next page...
 
/lp/association-for-computing-machinery/seth-based-lower-bounds-for-subset-sum-and-bicriteria-path-zd89nd962b
Publisher
Association for Computing Machinery
Copyright
Copyright © 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ISSN
1549-6325
eISSN
1549-6333
DOI
10.1145/3450524
Publisher site
See Article on Publisher Site

Abstract

Subset Sumand k-SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexity. An important open problem in this area is to base the hardness of one of these problems on the other.Our main result is a tight reduction from k-SAT to Subset Sum on dense instances, proving that Bellman’s 1962 pseudo-polynomial O*(T)-time algorithm for Subset Sum on n numbers and target T cannot be improved to time T1-ε · 2o(n) for any ε > 0, unless the Strong Exponential Time Hypothesis (SETH) fails.As a corollary, we prove a “Direct-OR” theorem for Subset Sum under SETH, offering a new tool for proving conditional lower bounds: It is now possible to assume that deciding whether one out of N given instances of Subset Sum is a YES instance requires time (N T)1-o(1). As an application of this corollary, we prove a tight SETH-based lower bound for the classical Bicriteria s,t-Path problem, which is extensively studied in Operations Research. We separate its complexity from that of Subset Sum: On graphs with m edges and edge lengths bounded by L, we show that the O(Lm) pseudo-polynomial time algorithm by Joksch from 1966 cannot be improved to Õ(L + m), in contrast to a recent improvement for Subset Sum (Bringmann, SODA 2017).

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Jan 22, 2022

Keywords: Subset sum

References

  • Subtree isomorphism revisited
    [,
  • Tight hardness results for LCS and other sequence similarity measures
    [,
  • The 4/3 additive spanner exponent is tight
    [,
  • Exact weight subgraphs and the k-Sum conjecture
    [,
  • Losing weight by gaining edges
    [,
  • Popular conjectures imply strong lower bounds for dynamic problems
    [,
  • Matching triangles and basing hardness on an extremely popular conjecture
    [,
  • More applications of the polynomial method to algorithm design
    [,
  • Consequences of faster alignment of sequences
    [,
  • Efficient testing of large graphs
    [,
  • Color-coding
    [,
  • On hardness of jumbled indexing
    [,
  • The constrained shortest path problem
    [,
  • Space–time tradeoffs for subset sum: An improved worst case algorithm
    [,
  • Subset sum in the absence of concentration
    [,
  • Dense subset sum may be the hardest
    [,
  • Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
    [,
  • Which regular expression patterns are hard to match?
    [,
  • On the fine-grained complexity of empirical risk minimization: Kernel methods and neural networks
    [,
  • Average-case fine-grained hardness
    [,
  • Proofs of useful work
    [,
  • Faster space-efficient algorithms for subset sum, k-sum and related problems
    [,
  • Subquadratic algorithms for 3SUM
    [,
  • Subquadratic algorithms for algebraic generalizations of 3SUM
    [,
  • Strong ETH holds for regular resolution
    [,
  • Improved generic algorithms for hard knapsacks
    [,
  • On sets of integers which contain no three terms in arithmetical progression
    [,
  • Dynamic Programming
    [,
  • On the quantitative hardness of CVP
    [,
  • The complexity of linear dependence problems in vector spaces
    [,
  • Cryptanalysis: A survey of recent results
    [,
  • Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
    [,
  • A near-linear pseudopolynomial time algorithm for subset sum
    [,
  • A dichotomy for regular expression membership testing
    [,
  • Quadratic conditional lower bounds for string problems and dynamic time warping
    [,
  • Complexity of single machine scheduling subject to nonnegative inventory constraints
    [,
  • Hardness of approximation for knapsack problems
    [,
  • Pattern matching under polynomial transformation
    [,
  • A duality between clause width and clause density for SAT
    [,
  • The complexity of satisfiability of small depth circuits
    [,
  • Solving k-SUM using few linear queries
    [,
  • Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
    [,
  • The parameterized complexity of domination-type problems and application to linear codes
    [,
  • Clustered integer 3SUM via additive combinatorics
    [,
  • Multi-party protocols
    [,
  • A knapsack-type public key cryptosystem based on arithmetic in finite fields
    [,
  • Matrix multiplication via arithmetic progressions
    [,
  • On problems as hard as CNF-SAT
    [,
  • Worst-case upper bounds
    [,
  • Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
    [,
  • Efficient dissection of composite problems, with applications to cryptanalysis, knapsacks, and combinatorial search problems
    [,
  • An improved construction of progression-free sets
    [,
  • An improved FPTAS for the restricted shortest path problem
    [,
  • New lower bounds for convex hull problems in odd dimensions
    [,
  • Almost optimal lower bounds for problems parameterized by clique-width
    [,
  • Improved subquadratic 3SUM
    [,
  • On a class of O(n^2) problems in computational geometry
    [,
  • Completeness for first-order properties on sparse structures with algorithmic applications
    [,
  • Computers and Intractability: A Guide to the Theory of NP Completeness
    [,
  • A survey on multi-constrained optimal path computation: Exact and approximate algorithms
    [,
  • Improved bounds for 3SUM, k-SUM, and linear degeneracy
    [,
  • How hard is it to find (honest) witnesses?
    [,
  • Bicriterion path problems
    [,
  • Approximation schemes for the restricted shortest path problem
    [,
  • Simple analysis of graph tests for linearity and PCP
    [,
  • A multicommodity network-flow problem with side constraints on paths solved by column generation
    [,
  • Computing partitions with applications to the knapsack problem
    [,
  • New generic algorithms for hard knapsacks
    [,
  • Efficient cryptographic schemes provably as secure as subset sum
    [,
  • On the complexity of k-SAT
    [,
  • Which problems have strongly exponential complexity?J
    [,
  • 3SUM, 3XOR, triangles
    [,
  • Local reductions
    [,
  • Bin packing with fixed number of bins revisited
    [,
  • Bounding the running time of algorithms for scheduling and packing problems
    [,
  • The shortest route problem with constraints
    [,
  • Threesomes, degenerates, and love triangles
    [,
  • Reducibility among combinatorial problems
    [,
  • Knapsack Problems
    [,
  • A survey of 3SUM-hard problems
    [,
  • Parameterizing PWM-and profile-matching and knapsack by the feasible-weight solutions count
    [,
  • A faster pseudopolynomial time algorithm for subset sum
    [,
  • Higher lower bounds from the 3SUM conjecture
    [,
  • Approximation algorithms for multi-agent scheduling to minimize total weighted completion time
    [,
  • Deterministic time-space trade-offs for k-SUM
    [,
  • Known algorithms on graphs on bounded treewidth are probably optimal
    [,
  • Lower bounds based on the exponential time hypothesis
    [,
  • Saving space by algebraization
    [,
  • QoS routing on networks with uncertain parameters
    [,
  • A simple efficient approximation scheme for the restricted shortest path problem
    [,
  • Knapsack Problems: Algorithms and Computer Implementations
    [,
  • Hiding information and signatures in trapdoor knapsacks
    [,
  • Real-time scheduling with a budget
    [,
  • A short note on Merlin-Arthur protocols for subset sum
    [,
  • Reducing a target interval to a few exact queries
    [,
  • Sets of integers that do not contain long arithmetic progressions
    [,
  • The rise and fall of knapsack cryptosystems
    [,
  • On the possibility of faster SAT algorithms
    [,
  • An improved exponential-time algorithm for k-SAT
    [,
  • Dynamic programming on the word RAM
    [,
  • Where are the hard knapsack problems?Comput
    [,
  • Towards polynomial lower bounds for dynamic problems
    [,
  • A comparison of solution strategies for biobjective shortest path problems
    [,
  • Fast approximation algorithms for the diameter and radius of sparse graphs
    [,
  • A combined robot selection and scheduling problem for flow-shops with no-wait restrictions
    [,
  • A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem
    [,
  • The communication complexity of addition
    [,
  • Space-efficient randomized algorithms for K-SUM
    [,
  • Approximation of pareto optima in multiple-objective, shortest-path problems
    [,
  • A new algorithm for optimal 2-constraint satisfaction and its implications
    [,
  • Finding orthogonal vectors in discrete structures
    [,
  • Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk)
    [,
  • Finding, minimizing, and counting weighted subgraphs
    [,
  • Open problems around exact algorithms
    [,
  • Constraint-based routing in the internet: Basic principles and recent research
    [,
  • Computer aided scheduling of switching engines
    [,