Improved space bounds for subset sum
From MaRDI portal
Cites work
- A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
- A short note on Merlin-Arthur protocols for subset sum
- Color-coding
- Computing Partitions with Applications to the Knapsack Problem
- Deterministic time-space trade-offs for k-SUM
- scientific article; zbMATH DE number 7829235 (Why is no real title available?)
- Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
- Local reductions
- More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
- New generic algorithms for hard knapsacks
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- Primality testing with Gaussian periods
- Relations Among Complexity Measures
- Subset sum in time \(2^{n/2}/\text{poly}(n)\)
This page was built for publication: Improved space bounds for subset sum
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7253076)
