0
$\begingroup$

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?

Source: https://www.math.uni-hamburg.de/home/schacht/abstracts/09eurocomb.pdf

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ "choosing a hypergraph at random is very unlikely to give you one that's hard" How unlikely? What percent? $\endgroup$
    – Jesus is Lord
    Commented Apr 4, 2020 at 2:08
  • $\begingroup$ "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? $\endgroup$
    – Jesus is Lord
    Commented Apr 4, 2020 at 2:13
  • $\begingroup$ @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.) $\endgroup$
    – D.W. ♦
    Commented Apr 4, 2020 at 2:33
  • $\begingroup$ @WordsLikeJared, negligible (smaller than one over any polynomial). $\endgroup$
    – D.W. ♦
    Commented Apr 4, 2020 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.