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
Error creating thumbnail: Unable to save thumbnail to destination
Step Chart
Error creating thumbnail: Unable to save thumbnail to destination
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | [Outside-In algorithm (1991)] | |
| Polynomial > 3 | ||
| Cubic | ||
| Quadratic | ||
| nlogn | ||
| Linear | ||
| logn |