Deciding bipartite hypergraph coloring is NP-hard:
While for bipartite graphs a 2-coloring can be found in linear time, it was shown by Lovasz  that the problem to decide whether a given k-uniform hypergraph is bipartite is NP-complete for all
Bipartite hypergraphs are colorable in expected (average) polynomial time:
The purpose of this note is to present an algorithm that colors a hyper-graph chosen uniformly at random from the family of all labeled, 3-uniform, bipartite hypergraphs on
O(n^5 * log (2n))expected time.
Does this imply that P is approximately NP?