I have a very simple question and wanted to check whether my answer is correct.
Suppose we are given a list of comparisons $x_1>x_2,..,x_k>x_i$ then consider the decision problem asks whether the ordering $>$ can be made transitive and complete over all the X.
My impression is that such a decision problem is NP-complete. Here is my proposed solution.
- Any solution can be checked in polynomial time, suffice to verify each comparison from the solution ordering.
- To show it is NP-complete, I show that the Betweenness Problem with triple type (https://en.wikipedia.org/wiki/Betweenness) is reducible to ours.
Proof of 2):
The Betweenness problem asks exactly our question but has ordering of type $x_1>x_2>x_3$.
But of course each such statement can be translated to $x_1>x_2$, $x_2>x_3$ this is done in at most (?) than polynomial time.
I just wanted to check whether this solution is correct and complete? Any help is greatly appreciated, thanks a lot!