Let $M$ be a deterministic Turing Machine over $\{0, 1\}$ which halts on every input. Let's consider the following problem:
It is given boolean circuit $C$. $C$ has $n$ input gates.
Problem:
- Is the $C$ equivalent to $M$ for words of $n$ length?
- Can you estimate the complexity independent of complexity $M$?
1.. Yes, we can construct a such machine:
Let $C$ be any boolean circuit which has $n$ input gates. Now, our machine gets $C$ and $M$ and test (simulate) both models on every words from $\{0,1\}^n$. If for some words the result is different for $M$ and $C$, reject $C$.
- It is not possible because we have to simulate that machine, so we depends on it. ( I'm afraid that it is too informal).
Is my solution right?