How do we test if an model or algorithm is AI-complete?

Question

How do we test if a model or algorithm is AI-complete?

Answer 1

According to the Wikipedia definition, a problem is said to be AI-complete if it requires generalized, human-level intelligence, that is, requires strong AI. The Turing test and its variants are the best ways we have of measuring this. See, for example, Turing Test as a Defining Feature of AI-Completeness.

As suggested in this paper, in order for the Turing test to be meaningful, the interrogator has a responsibility to ask questions which are both deep and meaningful.

It, therefore, seems likely that testing for strong AI is in itself an AI-complete task.