Skip to content

Subset Sum to Quadratic Diophantine Equation

SOberhoff edited this page Mar 11, 2018 · 1 revision

The namespace tnoc.subset-diophantine implements the reduction from Subset Sum to Quadratic Diophantine Equation detailed on pages 150 and following.

For example the weights [1 2] and the target value 2 are a satisfiable instance of Subset Sum. These produce the Quadratic Diophantine Equation

(subset-diophantine [1 2] 2)
=> (fn [x y] (= (+' (*' 2075941759359391 x x) (*' 182250000 y)) 605819780586669854621599N))

which is indeed satisfied by

(find-X-Y [1 2] 2)
=> [-14167 1037970897919001N]
Clone this wiki locally