0

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:

  1. Is the $C$ equivalent to $M$ for words of $n$ length?
  2. 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$.

  1. 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?

  • https://cs.stackexchange.com/q/74453/755 – D.W. Apr 25 '17 at 00:00
  • @D.W. - except that proof verification - the same issue that put the question on hold there - is actually a fairly common request here. – Paul Sinclair Apr 25 '17 at 02:37
  • @PaulSinclair, yup! I didn't mean to imply it's not suitable here. I just thought that I'd link the two together, as it looked like the question got an interesting comment over there which folks here might want the chance to see. – D.W. Apr 25 '17 at 06:58

0 Answers0