The asymptotic running-time computational complexity of this decision problem is at least doubly exponential, however, as shown by Fischer & Rabin (1974).
この決定問題の計算複雑性は漸近的に二重指数関数であることがFischer & Rabin (1974)で示されている。