<p>&quot;Complex&quot; problems are normally defined as problems which cannot be solved by (probabilistic) polynomial-time Turing machines.</p>
<p>When there are extra information available for solving the problem, the model changes to machines which take advice. That is, instead of <span class="math-container">$\rm{BPP}$</span> machines, we consider <span class="math-container">$\rm{P/poly}$</span>  circuits; i.e. polynomial-size circuits (equivalently, polynomial-time Turing machines which take polynomial advice).</p>
<p>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 <span class="math-container">$n^{\log n}$</span>). One might note that, an <strong>exponential-size</strong> 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 <span class="math-container">$O(n2^n)$</span>.)</p>
<p>Let's consider the <a href="http://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption" rel="nofollow noreferrer">Decisional Diffie-Hellman</a> (DDH) assumption.
I don't go into details. Just assume that <span class="math-container">$p$</span> is a large prime, all computations are over <span class="math-container">$\mathbb{Z}^*_p$</span>, and <span class="math-container">$g$</span> is its generator.</p>
<blockquote>
<p><strong>DDH:</strong> Distinguishing <span class="math-container">$(g,g^a,g^b,g^{ab})$</span> from <span class="math-container">$(g,g^a,g^b,g^c)$</span> is hard for probabilistic polynomial-time (<span class="math-container">$\rm{PPT}$</span>) machines.</p>
</blockquote>
<p>A <strong>stronger</strong> assumption is:</p>
<blockquote>
<p><strong>DDH-1:</strong> Distinguishing <span class="math-container">$(g,g^a,g^b,g^{ab})$</span> from <span class="math-container">$(g,g^a,g^b,g^c)$</span> is hard for <span class="math-container">$\rm{P/poly}$</span> circuits.</p>
</blockquote>
<p>An even <strong>stronger</strong> assumption is:</p>
<blockquote>
<p><strong>DDH-2:</strong> Distinguishing <span class="math-container">$(g,g^a,g^b,g^{ab})$</span> from <span class="math-container">$(g,g^a,g^b,g^c)$</span> is hard for sub-exponential circuits.</p>
</blockquote>
<p>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.</p>
<p>One example of <em>sub-exponential hardness assumption</em> is that, some languages in <span class="math-container">$\rm{E}$</span> don't have sub-exponential circuits. Such assumption is used by Impagliazzo &amp; Wigderson in <a href="http://www.math.ias.edu/%7Eavi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf" rel="nofollow noreferrer">P=BPP unless E has sub-exponential circuits:
Derandomizing the XOR Lemma</a>.</p>
<hr />
<h2>Description of Some Terms</h2>
<p>While obvious, I'm going to define several terms here. Let <span class="math-container">$f \colon \mathbb{N} \to \mathbb{N}$</span> be a function. Then:</p>
<ul>
<li><span class="math-container">$f(n) = n^{\Theta(1)}$</span> is called <em>polynomial</em>. (e.g. <span class="math-container">$n, n^3, 7n^{100}$</span>.)</li>
<li><span class="math-container">$f(n) = n^{\omega(1)}$</span> is called <em>super-polynomial</em>. (e.g. <span class="math-container">$n^{\log n}, 2^n, 2^{2^n}$</span>.)</li>
<li><span class="math-container">$f(n) = 2^{\Theta(n)}$</span> is called <em>linear exponential</em>. (e.g. <span class="math-container">$2^n, 3^n, 10^n$</span>.)</li>
<li><span class="math-container">$f(n) = 2^{n^{\Theta(1)}}$</span> is called <em>exponential</em>. (e.g. <span class="math-container">$2^n, 3^{n^4}$</span>.)</li>
<li><span class="math-container">$f(n) = 2^{n^{o(1)}}$</span> is called <em>sub-exponential</em>. (e.g. <span class="math-container">$2^{n^{1/n}}, n^{\log n}$</span>.)</li>
</ul>

CC BY-SA 4.0
2010-11-23T18:02:35.677Z
2022-05-10T08:50:43.307Z
2022-05-10T08:50:43.307Z
Sadeq Dousti
<p><strong>Edited</strong><br />
I want to read more about subexponential hardness assumption, but I didn't find any good survey on this. I just took a look at <a href="https://en.wikipedia.org/wiki/Heavy-tailed_distribution" rel="nofollow noreferrer">Heavy-tailed distribution</a> and <a href="https://doi.org/10.1007/BF02356073" rel="nofollow noreferrer">Some properties of subexponential distributions</a> but I didn't get a good picture of it.</p>
<blockquote>
<p><strong>Question</strong>: What is the subexponential hardness assumption? Is it a weaker hardness assumption in comparison with discrete logarithm? Do you know any good survey or article on this?</p>
</blockquote>
<p>I saw this subject in this paper:<br />
<a href="http://www.cs.cornell.edu/%7Erafael/papers/ccacommit.pdf" rel="nofollow noreferrer"> Adaptive hardness and composable security in the plain model from standard assumptions</a></p>

CC BY-SA 2.5
2010-11-23T12:56:44.680Z
I do not think that I know the answer anyway, but can you provide more information about the term “sublinear hardness assumption”?  For example, the context where the term appears will be hopefully helpful.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-23T17:13:26.243Z
I've never heard of a sublinear hardness assumption either
Suresh Venkat
CC BY-SA 2.5
2010-11-23T17:47:29.857Z
Sorry! My bad! Two subjects got mixed together! Please see the edited text
Yasser Sobhdel
CC BY-SA 2.5
2010-11-23T18:44:44.990Z
the reference you link to nowhere mentions "subexponential hardness assumption". It talks about subexponential hardness which I assume implies hardness of solution in subexponential time ?
Suresh Venkat
CC BY-SA 2.5
2010-11-23T20:16:30.367Z
@Suresh: I don't get what you mean by "the reference you link to nowhere". I have changed the topic from the original post and I think the Sadeq answer below is more to the point.
Yasser Sobhdel
<cc.complexity-theory><cr.crypto-security><complexity-assumptions>
Subexponential hardness assumption
Yasser Sobhdel
# Subexponential hardness assumption

(Asked by: username_0 on 2010-11-23)

**Edited**  
I want to read more about subexponential hardness assumption, but I didn't find any good survey on this. I just took a look at [Heavy-tailed distribution](https://en.wikipedia.org/wiki/Heavy-tailed_distribution) and [Some properties of subexponential distributions](https://doi.org/10.1007/BF02356073) but I didn't get a good picture of it.

> **Question**: What is the subexponential hardness assumption? Is it a weaker hardness assumption in comparison with discrete logarithm? Do you know any good survey or article on this?

I saw this subject in this paper:  
 [Adaptive hardness and composable security in the plain model from standard assumptions](http://www.cs.cornell.edu/%7Erafael/papers/ccacommit.pdf)

**Tags:** cc.complexity-theory, cr.crypto-security, complexity-assumptions
> **Comments:**
> **username_1**: I do not think that I know the answer anyway, but can you provide more information about the term “sublinear hardness assumption”?  For example, the context where the term appears will be hopefully helpful.  
> **username_2**: I've never heard of a sublinear hardness assumption either  
> **username_0**: Sorry! My bad! Two subjects got mixed together! Please see the edited text  
> **username_2**: the reference you link to nowhere mentions "subexponential hardness assumption". It talks about subexponential hardness which I assume implies hardness of solution in subexponential time ?  
> **username_0**: @Suresh: I don't get what you mean by "the reference you link to nowhere". I have changed the topic from the original post and I think the Sadeq answer below is more to the point.  

---

## 1 answers

### Answer by username_3 on 2010-11-23. Score: 12 | Accepted answer

"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](http://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption) (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](http://www.math.ias.edu/%7Eavi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf).

---

## 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}$.)


---

