We present a natural model of network computing that is closely related to the 
network coding model of Ahlswede, Cai, Li, and Yeung and introduce the notions 
of computing capacity and solvability  for a given network and a target function.
Borrowing ideas from communication complexity and graph theory, we obtain an upper bound 
on the computing capacity for arbitrary target functions and networks. 
In addition, lower bounds on the computing capacity are given for several subclasses 
of target functions.

We introduce the notion of linearly-reducible target functions and 
show that linear network codes may provide a computing capacity advantage over routing only
when the receiver demands a linearly-reducible target function. Many known target 
functions including the arithmetic sum, minimum, and maximum are not linearly-reducible.
Thus, the use of non-linear codes is essential in order to obtain a computing 
capacity advantage over routing if the receiver demands a target function that 
is not linearly-reducible.

We consider the scenario in which the source alphabet is a finite field and the target 
function is linear and obtain an algebraic characterization to test whether an arbitrary network can compute 
a linear target function using linear codes.
We identify a class of linear functions that can be computed using linear codes 
in every network that satisfies a natural cut-based condition.
Conversely, for another class of linear functions, we show that the cut-based condition 
does not guarantee the existence of a linear coding solution.