In [32] it is shown that one can formulate the problem as a combinatorial optimization problem, for which a strongly dual problem in the sense of combinatorial optimization exists (see the comments to Problem 16). Thus, the AOF-orientations of G_P have a good characterization (see Problem 17) in terms of G_P, i.e., there are polynomial size proofs for both cases an orientation being an AOF-orientation or not (provided that the integrity of the input data is guaranteed). However, it is unknown if it is possible to check in polynomial time if a given orientation is an AOF-orientation.

In dimensions one and two the problem is trivial. For a three-dimensional polytope P the problem can be solved in polynomial time, e.g., by producing a plane drawing of G_P with convex faces (see Tutte [64]) and sorting the nodes with respect to a linear function (in general position).

A polynomial time algorithm would lead to a polynomial algorithm for Problem 17 (see [32]).

By duality of polytopes, the problem is equivalent to the problem of finding a shelling order of the facets of a simplicial polytope from the upper two layers of its face lattice. It is unknown whether it is possible to find in polynomial time a shelling order of the facets, even if the polytope is given by its entire face lattice. With this larger input, however, it is possible to check in polynomial time whether a given ordering of the facets is a shelling order.