Turnpike problem

Problem Description

The turnpike problem, also known as the partial digest problem, is: Given a multiset of (:) positive numbers AX, does there exist a set X such that AX is exactiy the multiset of al1 positive pairwise difierences of the elements of X. The complexity of the problem is aot known.

Bounds Chart

Step Chart

Improvement Table

Complexity Classes	Algorithm Paper Links	Lower Bounds Paper Links
Exp/Factorial	[Outside-In algorithm (1991)]
Polynomial > 3
Cubic
Quadratic
nlogn
Linear
logn