# If there is an polynomial time approximation to an NP-complete problem, is P approximately NP?

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 [10] that the problem to decide whether a given k-uniform hypergraph is bipartite is NP-complete for all k≥3.

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 n vertices in O(n^5 * log (2n)) expected time.

Does this imply that P is approximately NP?

No, it doesn't prove that P = NP.

This has nothing to do with approximations; it has to do with average-case hardness vs worst-case hardness. The two results are showing that solving the problem for a randomly chosen hypergraph is usually easy; but there exist hypergraphs where the problem is hard. Presumably, choosing a hypergraph at random is very unlikely to give you one that's hard, but they do exist.

NP-completeness is about worst-case hardness: even if a problem is easy on average, it can still be NP-complete.

I have no idea what "P is approximately NP" would mean in any precise sense.

• "choosing a hypergraph at random is very unlikely to give you one that's hard" How unlikely? What percent? Apr 4, 2020 at 2:08
• "This has nothing to do with approximations; it has to do with average-case hardness vs worst-case hardness. " Does that mean a polynomial approximation is worst-case polyonmial time, but sometimes answers incorrectly; a polynomial expected always answers correctly but worst-case time exceeds polynomial? Apr 4, 2020 at 2:13
• @WordsLikeJared, I recommend reviewing en.wikipedia.org/wiki/Approximation_algorithm for definitions. An approximation algorithm is one that has a guarantee on the quality of its output; a polynomial-time approximation algorithm is an approximation algorithm that runs in polynomial time, i.e., whose worst-case running time is polynomial. (A PTAS or FPTAS is different.)
– D.W.
Apr 4, 2020 at 2:33
• @WordsLikeJared, negligible (smaller than one over any polynomial).
– D.W.
Apr 4, 2020 at 2:35