The authors treat the space \({\mathcal H}\{M_ p\}\) of smooth functions \(\phi\) (x) on R such that for every \(p\in {\mathbb{N}}\) \(\gamma_ p(\phi):=\sup \{| \phi^{(j)}(x)| \cdot \exp (M_ p(x));x\in R,0\leq j\leq n\}0\), continuous differentiable functions. We can easily see that S*T is also contained in \({\mathcal H}'\{M_ P\}\) for \(s\in {\mathcal O}_ c'({\mathcal H}\{M_ p\})\) and for every \(t\in {\mathcal H}'\{M_ p\}\). The contents of this paper is the proof of the following Main Theorem: Suppose that \(S\in {\mathcal O}_ c'({\mathcal H}'\{M_ p\})\) and that \(\hat S(\)w), \(w=u+iv\in {\mathbb{C}}\), is the Fourier transform of S. Then the following three propositions are equivalent: \((H_ 1)\) S is hypoelliptic in \({\mathcal H}'\{M_ p\}\) (i.e., S*T\(\in {\mathcal H}'\{M_ p\}\Rightarrow T\in {\mathcal H}'\{M_ p\});\) \((H_ 2)\) (a) There exist B, \(M>0\) such that \(| \hat S(u)| \geq | u|^{-B}\) for \(| u| \geq M;\) (b) For each \(p\in {\mathbb{N}}\), \(\lim(\tilde M_ p(v)/\log | w|)=\infty\) when \(| w| \to \infty\) for w staying on the surface \(\hat S(\)w)\(=0;\) \((H_ 3)\) For every \(p\in N\) and \(d>0\) there exists a constant \(\bar B>0\) such that for every \(m\in {\mathbb{N}}\) there exists \(C_ m>0\) with the property \(| 1/\hat S(w)| \leq | w|^{\bar B}\) exp(d\(\cdot \tilde M_ p(v))\) for \(| \tilde M_ p(v)| \leq m \log | w|\) and \(| w| \geq C_ m.\) Here \(\tilde M_ p(v)\) denotes the dual function of \(M_ p(x)\) in the sense of Young. Let \(\{\) N(x)\(\}\) be a monotonically increasing sequence of even, smooth non-negative functions such that for \(x>1\) \(N_ p(x)=\int_{R}M_ p(t)\omega (x-t)dt\) (regularization of \(M_ p(t))\) and \(\{\) Ṉ\({}_ p(x)\}\) be the sequence \(\{N_ p(x)\}\) of functions increasing for \(x>0\). They use the condition \((H_ 3')\) obtained from \((H_ 3)\) by inserting Ṉ\({}_ p(v)\) instead of \(\tilde M_ p(v)\). They also use the (p,q)-parametrix \(P\in {\mathcal H}'\{M_ p\}\) for \(s\in {\mathcal O}_ c'({\mathcal H}'(M_ p))\) satisfying the following two conditions: \((P_ 1)\) There exists \(n\in {\mathbb{N}}\) and a continuous function F(x) on R with the property \(F(x)=O(\exp (-N_ p(x)))\) as \(| x| \to \infty\) satisfying \(P(x)=D^ nF(x).\) \((P_ 2)\) If \(W(x):=\delta (x)-(S*P)(x)\), then \(W\in C^ q(R)\) and \(W^{(j)}(x)=0(\exp (-N_ p(x)))\) as \(| x| \to \infty\) for \(0\leq \forall j\leq q\) and every \(p\in {\mathbb{N}}.\) The most essential part of their proof, \((H_ 3)\Rightarrow (H_ 1)\), is derived by showing the existence of the (p,q)-parametrix for S under the condition \((H_ 3')\) equivalent to \((H_ 3)\).