A product of Kripke frames is the product of their underlying sets with the original relations preserved along the corresponding coordinates. Products of frames and products of logics were introduced by the reviewer [Math. Notes 23, 417-424 (1978); translation from Mat. Zametki 23, 759-772 (1978; Zbl 0384.03010)] and intensively studied recently [cf. \textit{D. Gabbay} and \textit{V. Shehtman}, Log. J. IGPL 6, 73-146 (1998; Zbl 0902.03008); ibid. 8, 165-210 (2000) for further references]. The paper proves several non-trivial results on complexity of product logics. All lower bounds are obtained by tiling arguments. It is shown that the product of every two logics among K, D, T, K4, S4, S5 has a NEXPTIME-hard satisfaction problem. The situation with upper bounds within the same set of product logics is more difficult. In some cases (e.g. for \(\text{K}\times \text{K}\), \(\text{K}\times \text{K}4\)) only Kalmar non-elementary upper bounds are known [\textit{D. Gabbay} and \textit{V. Shehtman} (1998), loc. cit.; \textit{F. Wolter}, ``The product of converse PDL and polymodal K'', J. Log. Comput. 10, No. 2, 223-251 (2000)]. All these logics are known to be RE [cf. \textit{D. Gabbay} and \textit{V. Shehtman} (1998), loc. cit.], and decidability remains an open problem for some of them (e.g. for \(\text{K4}\times \text{K4}\)). However, the paper proves that the satisfaction problem in \(\text{S5}\times \text{K}\) is NEXPTIME-complete; for \(\text{S5}\times \text{S5}\) this follows from a paper of \textit{E. Grädel, P. Kolaitis} and \textit{M. Vardi} [Bull. Symb. Log. 3, 53-69 (1997; Zbl 0873.03009)]. It is also proved that for any complete monomodal logic L, the products \(\text{L}\times \text{Alt}_1\), \(\text{L}\times \text{SL}\) (where \(\text{Alt}_1= \text{K} +\neg p\rightarrow\neg p\), \(\text{SL}= \text{K}+\neg p\leftrightarrow\neg p\)) have the same complexity as L. On the other hand, it is shown that the global satisfaction problem, i.e. the problem whether a given formula is globally true in some model over an L-frame, is undecidable if L is a product logic, such as \(\text{Alt}_1^2\), \(\text{K}^2\) etc.