Also, this algorithm is not easily parallelizable, so even O(n^5) can be an issue for n > 1000.

Also note that in this particular problem, n is a count of bits and logical ORs of pairs of bits, so getting to n > 1000 is a lot easier than you may think.

Many NP-hard problems tend not to be NP-hard on "average"; that is, reasonable heuristics can usually find you the correct answer. But there are certain structures that are (seemingly) difficult to solve. If you can exclude these structures by construction, the problem is in P; otherwise it's NP-hard. Boolean satisfiability is a good example here.

It also turns out from combinatorics that you can sometimes force necessary order on a structure by embedding it in larger space--sheer size imposes a structure of its own. Probably the most well-known example of this is the L=SL proof (admittedly, not generally well-known), where you can guarantee a walk that will visit all connected nodes of a graph without saving any history of nodes you've visited. Just replace every node with a new graph that is of size at least (IIRC) 3^65536. It's a constant factor, even if the constant is larger than the volume of the universe measured in Planck lengths.