To me, whether it's NP-complete is of little concern, since humans have been allocating registers (and beating compilers) with little difficulty. On the contrary, I feel that being labeled as NP-complete has somehow slowed the development of better RA algorithms, on the basis that it's "too hard". There's a saying "one of the first steps to accomplishing something is to believe that it's possible", and if people believe that RA is a more difficult problem than it really is, then that has a discouraging effect. NP-completeness is only related to the complexity as the problem size increases, but in practice the problem sizes aren't that big --- e.g. within a function, having several dozen live variables at a time is probably extremely uncommon, and machines don't have that many registers - a few dozen at most.

I think the human brain is probably Turing-equivalent, but it also likely doesn't matter -- if I can describe the algorithm that I, as a human, take to perform compiler-beating register allocation and instruction selection, then a machine can probably do it just as well if not faster than me since it can consider many more alternatives and at a much faster rate.

I agree that heuristic approaches are the way to go, but in a "too far abstracted" model like graph colouring, some heuristics just can't be easily used; e.g. the technique of "clearing the table" --- setting up all the registers prior to a tight loop, so that the instructions within do not have to access memory at all. Using push/pop (x86) for "very ephemerally-spilled" values is another one.

> To me, whether it's NP-complete is of little concern, since humans have been allocating registers (and beating compilers) with little difficulty.

Following that logic, one would conclude that writing an AI for Go is trivial as well [1].

> if I can describe the algorithm that I, as a human, take ... then a machine can probably do it just as well if not faster

This is pretty easy to disprove. You can probably look at a program's source code and tell whether or not it halts. But it's been proven that a Turing machine cannot [2]. The halting problem is one of many undecidable problems in computer science [3]. If any one of the undecidable problems can be solved by a human, that proves that the human brain is not Turing equivalent.

[1] https://en.wikipedia.org/wiki/Computer_Go

[2] https://en.wikipedia.org/wiki/Halting_problem

[3] https://en.wikipedia.org/wiki/Undecidable_problem

I think you misunderstand what is the halting problem. It's being able to tell whether a program will halt or not, for all conceivable programs. A human brain certainly can't do that.

For example, does this program halt? (Let's assume infinite-precision numbers, for simplicity. After all, a Turing machine can access an infinitely long tape.)

    for (int n = 3; ; n++)
      for (int a = 1; a < n; a++)
        for (int b = 1; b < n; b++)
          for (int c = 1; c < n; c++)
            for (int m = 3; m < n; m++)
              if (pow(a, m) + pow(b, m) == pow(c, m)) exit(1);

Show me that this program never halts, and you just proved Fermat's last theorem.

Edit: added one missing loop

AIs have been made for Go and they aren't extraordinarily complicated. They can beat most humans.

It's pretty widely believed that humans are Turing equivalent, and there is no evidence at all to suggest we aren't. Certainly humans can't determine halting for all possible programs and inputs. And we run on physics which as far as I know is Turing equivalent.