On the complexity of interval orders and semiorders (Q1088407)

For an order \(P_ 0\), the \(P_ 0\)-recognition problem is to decide whether an unknown order is isomorphic to \(P_ 0\) by means of pairwise comparisons of the elements in the underlying set. The identification problem asks to determine an unknown order without a priori information. An order \(P\) is called an interval order whenever \(P\) does not contain the order \(2+2\) as an induced suborder. A semiorder is an interval order which does not contain the order \(1+3\) as an induced suborder. Questions: (a) Is the recognition complexity \(\Omega (n \log_ 2n)\) for every order on \(n\) elements? (b) Is there an optimal identification algorithm? Results: (a) \(\Omega (n \log_ 2n)\) is the recognition complexity of interval orders. (b) An optimal algorithm is given for the identification of semiorders.