"Complex" problems are normally defined as problems which cannot be solved by (probabilistic) polynomial-time Turing machines.
When there are extra information available for solving the problem, the model changes to machines which take advice. That is, instead of $\rm{BPP}$ machines, we consider $\rm{P/poly}$ circuits; i.e. polynomial-size circuits (equivalently, polynomial-time Turing machines which take polynomial advice).
In some cases, we may consider even stronger solvers: Instead of poly-sized circuits, we may use circuits whose size is sub-exponential. (e.g. circuits whose size is $n^{\log n}$). One might note that, an exponential-size family of circuits can decide any language (even undecidable ones) by merely incorporating the look-up table in its code. (In particular, the size of the look-up table is $O(n2^n)$.)
Let's consider the Decisional Diffie-Hellman (DDH) assumption.
I don't go into details. Just assume that $p$ is a large prime, all computations are over $\mathbb{Z}^*_p$, and $g$ is its generator.
DDH: Distinguishing $(g,g^a,g^b,g^{ab})$ from $(g,g^a,g^b,g^c)$ is hard for probabilistic polynomial-time ($\rm{PPT}$) machines.
A stronger assumption is:
DDH-1: Distinguishing $(g,g^a,g^b,g^{ab})$ from $(g,g^a,g^b,g^c)$ is hard for $\rm{P/poly}$ circuits.
An even stronger assumption is:
DDH-2: Distinguishing $(g,g^a,g^b,g^{ab})$ from $(g,g^a,g^b,g^c)$ is hard for sub-exponential circuits.
I saw both DDH and DDH-1 assumptions in the literature. DDH-2 may also exist, but I can't recall whether I ever saw it.
One example of sub-exponential hardness assumption is that, some languages in $\rm{E}$ don't have sub-exponential circuits. Such assumption is used by Impagliazzo & Wigderson in P=BPP unless E has sub-exponential circuits:
Derandomizing the XOR Lemma.
Description of Some Terms
While obvious, I'm going to define several terms here. Let $f \colon \mathbb{N} \to \mathbb{N}$ be a function. Then:
- $f(n) = n^{\Theta(1)}$ is called polynomial. (e.g. $n, n^3, 7n^{100}$.)
- $f(n) = n^{\omega(1)}$ is called super-polynomial. (e.g. $n^{\log n}, 2^n, 2^{2^n}$.)
- $f(n) = 2^{\Theta(n)}$ is called linear exponential. (e.g. $2^n, 3^n, 10^n$.)
- $f(n) = 2^{n^{\Theta(1)}}$ is called exponential. (e.g. $2^n, 3^{n^4}$.)
- $f(n) = 2^{n^{o(1)}}$ is called sub-exponential. (e.g. $2^{n^{1/n}}, n^{\log n}$.)
