If we define $$\cal N _1 := \{ 1\} $$ and by induction $$\cal N_{n+1}:=\{x\in \mathbb N | \exists a,b \in\cal N_n : x= a+b \text{ or }x=ab \text{ or }x=a^b \}$$ it's easy to prove that, for every $m \in \mathbb N\backslash \{0\}$, there exists $n\le m$ such that $m\in \cal N_n$.
If we define $\deg (n):= \min\{m\in \mathbb N | \;n\in\cal N_m\} $ (let's call it degree of n), can you find a way to calculate the degree of every positive integer (which is at least better than brute force)?
It's very unlikely, even if you remove exponentiation and leave only addition and multiplication.
As Erdos said of the Collatz conjecture, "Mathematics is not yet ready for such problems." The difficulty is the mixture of addition and multiplication, which leaves the problem with little exploitable structure. Other very difficult problems of this nature, in addition to the Collatz conjecture, include the Goldbach conjecture, the infinitude of primes of the form $x^2+1$, etc.
While I'd be surprised if there were an easy way to exactly compute the degree of a number, you can of course try to prove bounds. One obvious improvement to p.s.'s, for composite numbers: $$\deg(n) \leq 1+\log_2 \omega(n) + \log_2 \max(P(n), Q(n))$$ where $P(n)$ is the largest prime in $n$'s prime factorization and $Q(n)$ is the largest power.