<p>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:</p>

<p>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$.</p>

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

CC BY-SA 2.5
2010-09-15T17:42:07.117Z
2010-09-15T17:42:07.117Z
Sadeq Dousti
<p>Assume that we are interested in deterministic circuits of size $f(n)$. Here, $n$ represents the number of inputs to the circuit.</p>

<p>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?</p>

<ol>
<li> $n$ is the number of deterministic inputs.
<li> $n$ is the number of deterministic PLUS probabilistic/nondeterministic inputs.
</ol>

<p>My confusion is that some references consider case 1, while others consider case 2.</p>

CC BY-SA 2.5
2010-09-13T17:04:28.960Z
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.
Ryan Williams
CC BY-SA 2.5
2010-09-13T17:45:51.207Z
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?
Sadeq Dousti
CC BY-SA 2.5
2010-09-13T20:55:05.593Z
Yes, there is an upper bound of $f(n)=2n$, as mentioned in my previous comment.
Ryan Williams
<cc.complexity-theory><circuit-complexity><nondeterminism><probabilistic-circuits>
On Defining Probabilistic/Nondeterministic Circuits
Sadeq Dousti
# On Defining Probabilistic/Nondeterministic Circuits

(Asked by: username_0 on 2010-09-13)

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.- $n$ is the number of deterministic PLUS probabilistic/nondeterministic inputs.

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

**Tags:** cc.complexity-theory, circuit-complexity, nondeterminism, probabilistic-circuits
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: Yes, there is an upper bound of $f(n)=2n$, as mentioned in my previous comment.  

---

## 1 answers

### Answer by username_0 on 2010-09-15. Score: 3 | Accepted answer

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>


---

