Comment by pron

Except deciding whether an implementation exists or not is itself not a tractable problem in the general case.