  In this paper the complexity of provability of polarized additive,
multiplicative, and exponential formulas in the (initial) Cockett-Seely
polarized game logic is discussed. The complexity is ultimately based on the
complexity of finding a strategy in a formula which is, for polarized additive
formulas, in the worst case linear in their size. Having a proof of a sequent
is equivalent to having a strategy for the internal-hom object. In order to
show that the internal-hom object can have size exponentially larger than the
formulas of the original sequent we develop techniques for calculating the size
of the multiplicative formulas.
  The structure of the internal hom object can be exploited and, using dynamic
programming techniques, one can reduce the cost of finding a strategy in such a
formula to the order of the product of the sizes of the original formulas. The
use of dynamic techniques motivates the consideration of games as acyclic
graphs and we show how to calculate the size of these graph games for the
multiplicative and additive fragment and, thus, the cost of determining their
provability using this dynamic programming approach.
  The final section of the paper points out that, despite the apparent
complexity of the formulas, there is, for the initial polarized logic with all
the connectives (additives, multiplicatives, and exponentials) a way of
determining provability which is \emph{linear} in the size of the formulas.
