Chỉnh sửa: Hãy để tôi thử và giải thích thêm. Đó là bởi vì thuật toán tìm kiếm các giải pháp hạn chế mà nó tìm thấy ở mức trung bình một sau đó $$\frac{(2^{d/3})^4}{2^d}=2^{d/3}$$ giải pháp có trong danh sách $L_i$ như được chọn bên dưới. Đây là cái giá phải trả cho sự phức tạp $2^{d/3}$ thay cho $2^{d/2}$ phức tạp của Shamir Schroeppel.
Lấy trường hợp $k=4,$ đó là khi bạn đang tìm kiếm một giải pháp
$$x_0+x_1+x_2+x_3=0,\quad x_i \in L_i$$ Wagner tạo ngẫu nhiên 4 danh sách $L_i~(1\leq i\leq 4)$ kích thước $2^{d/3}$ ở đâu $d$ là độ dài bit.
Bằng các lập luận thống kê, bạn sẽ có một giải pháp duy nhất với xác suất không đổi giới hạn từ 0 khi danh sách có kích thước $2^{d/4}$ (xem xét thực tế là có $(2^{d/4})^4=2^d$ 4 tổng có thể được rút ra từ các danh sách này và với xác suất không đổi là giá trị $0$ sẽ bị đánh). Nhưng vấn đề là không có cách hiệu quả nào để tìm giải pháp duy nhất này ngoại trừ phương pháp Shamir-Schroeppel có bộ nhớ hiệu quả nhưng độ phức tạp về thời gian $2^{d/2}.$
Những gì Wagner làm là tạo đệ quy các giải pháp, nhưng các giải pháp có cấu trúc đặc biệt. Phần ba bit đầu tiên của các ứng cử viên từ $L_0,L_1$ được khớp, tương tự cho $L_2,L_3$ vân vân.
Bởi vì các giải pháp được cấu trúc, bạn cần phải phát ra nhiều giải pháp hơn số lượng tối thiểu cần thiết để thuật toán của bạn tìm thấy một giải pháp duy nhất có xác suất tốt.
