Assume that we are interested in deterministic circuits of size $f(n)$. Here, $n$ represents the number of inputs to the circuit.

The standard way of defining probabilistic/nondeterministic circuits is to augment the input with inputs. Let's assume that the circuit is still of size $f(n)$. What is $n$ in this case?

  1. $n$ is the number of deterministic inputs.
  2. $n$ is the number of deterministic PLUS probabilistic/nondeterministic inputs.

My confusion is that some references consider case 1, while others consider case 2.

  • 5
    $\begingroup$ I don't think there is a standard for what $n$ is here. The "right" choice would depend on what is being proved about nondeterministic circuits. You'll have to look closely at the definitions (or the proofs themselves) to know which case you're dealing with. A well-written paper will say upfront which convention is being used. If case 1 is being used, then hopefully there is some function $g(n) \leq f(n)$ denoting the number of extra inputs. $\endgroup$ – Ryan Williams Sep 13 '10 at 17:04
  • $\begingroup$ OK. Let's assume that $f(n)=2n$, and case 1 is being used. Moreover, assume that gates are ANDs and XORs, with fan-in 2, and unbounded fan-out. Then, I think there's an obvious upper-bound on the number of probabilistic/nondeterministic inputs, without explicitly introducing some function $g$. Am I right? $\endgroup$ – M.S. Dousti Sep 13 '10 at 17:45
  • 2
    $\begingroup$ Yes, there is an upper bound of $f(n)=2n$, as mentioned in my previous comment. $\endgroup$ – Ryan Williams Sep 13 '10 at 20:55

I found the following text in [1] (cited below); it shows that---as Ryan pointed out---there must be some function limiting the number of nondeterministic/random inputs; unless it can be judged from other things without ambiguity:

We develop nondeterministic $\mathbf{NC}$ ($\mathbf{NC}$) circuits by uniformly adding guessing gates to families of $\mathbf{LOGSPACE}$-uniform $\mathbf{NC}$ circuits. Let $\mathbf{NNC}(f(n))$ be the class of languages accepted by $\mathbf{LOGSPACE}$-uniform families of $\mathbf{NC}$ circuits with $O(f(n))$ nondeterministic gates or guess gates, where $n$ is the length of the input. We will refer to a circuit from such a family as a uniform $\mathbf{NNC}$ circuit, and such a circuit accepts an input if it outputs a 1. The guessing gates give the circuit a set of guessing inputs, $y$, in addition to the ordinary inputs, $x$. Note that $|x|=n$ and $|y|=f(n)$. An $\mathbf{NNC}$ circuit is said to accept $x$ if and only if there is some string of guessing bits $y$ that causes the circuit to output a 1. Thus, $f(n)$ can be thought of as the maximum number of guess bits used in computations on inputs of length $n$.

[1] Wolf, M. J. 1994. Nondeterministic circuits, space complexity and quasigroups. Theor. Comput. Sci. 125, 2 (Mar. 1994), 295-313. DOI= http://dx.doi.org/10.1016/0304-3975(92)00014-I


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.