Turnpike problem
Revision as of 11:01, 10 October 2022 by Admin (talk | contribs) (Created page with "== 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 == 1050px == Step Chart == 1050px == Improvement Table == {| class="wikit...")
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 |