<p>Assuming that $P \ne NP$ 
how surprising would it be if a weaker form of $P = NP$ holds? </p>

<p>For example consider the following weaker forms of $P = NP$:</p>

<ol>
<li><p>$NP \subseteq DTime(2^{O(n^\varepsilon)})$ for some $\varepsilon &lt; 1$.</p></li>
<li><p>$NP \subseteq DTime(2^{cn})$ for some constant $c &lt; 1$.</p></li>
<li><p>$NP \not\subseteq DTime(2^{O(n^\varepsilon)})$ for any $\varepsilon &lt; 1$, but 
there is an efficient algorithm 
that solves all (or say 99% of) instances that come up in practice.<br>
E.g. there is some efficiently computable set of inputs and
an efficient algorithm that solves the promise problem on that set.
The set contains all "real-world" instances of the problem.</p></li>
<li><p>$NP \not\subseteq DTime(2^{O(n^\epsilon)})$ for any $\epsilon &lt; 1$, but 
there is an efficient probabilistic algorithms 
that is correct with probability $p$ (where $p &lt; 1$).</p></li>
</ol>

<p>5-8. 1-4 above with a quantum computer.</p>

<p>How surprising would any of these statements be to theoreticians 
compared to $P = NP$?</p>

CC BY-SA 3.0
2015-12-09T14:27:26.237Z
This is quite a broad and open ended question..The conjecture that 1. does not happen is the Exponential Time Hypothesis (ETH). The conjecture that 2. does not happen is the Strong Exponential Time Hypothesis (SETH). If you search with these keywords you will find a lot of information about these two. In 4 if the running time of the algorithm is polynomial for p bounded away from 1/2, then you get NP = BPP $\subset$ P\poly which would be quite a surprise and has many consequences, see the Karp-Lipton theorem.
Sasho Nikolov
CC BY-SA 3.0
2015-12-11T02:35:15.077Z
@Sasho Nikolov: Interesting. What if in #4, the algorithm is not polynomial for any $p$, but is subexponential for all $0 \le p < 1$?
The_Sympathizer
CC BY-SA 3.0
2015-12-12T06:15:34.037Z
@Ricky Demer: How does "1% NP 'instances in practice'" imply that no OWFs? If the algorithm requires, say, a structured input and the OWF was given a pseudo-random input, like the hash off a crypto hash algorithm, then the algorithm would fail to invert the OWF. Looking it up, it seems that OWFs are defined in terms of random input, so an algorithm that solves for structured inputs would be useless for random ones, and thus couldn't they still be OW by the definition given?
The_Sympathizer
CC BY-SA 3.0
2015-12-14T13:30:40.193Z
@SashoNikolov Consider converting your comment into an answer.
Mohammad Al-Turkistany
<cc.complexity-theory>
Possibility of weaker forms of $P = NP$
The_Sympathizer
# Possibility of weaker forms of $P = NP$

(Asked by: username_0 on 2015-12-09)

Assuming that $P \ne NP$
how surprising would it be if a weaker form of $P = NP$ holds?

For example consider the following weaker forms of $P = NP$:

1. $NP \subseteq DTime(2^{O(n^\varepsilon)})$ for some $\varepsilon < 1$.
2. $NP \subseteq DTime(2^{cn})$ for some constant $c < 1$.
3. $NP \not\subseteq DTime(2^{O(n^\varepsilon)})$ for any $\varepsilon < 1$, but
   there is an efficient algorithm
   that solves all (or say 99% of) instances that come up in practice.  
   E.g. there is some efficiently computable set of inputs and
   an efficient algorithm that solves the promise problem on that set.
   The set contains all "real-world" instances of the problem.
4. $NP \not\subseteq DTime(2^{O(n^\epsilon)})$ for any $\epsilon < 1$, but
   there is an efficient probabilistic algorithms
   that is correct with probability $p$ (where $p < 1$).

5-8. 1-4 above with a quantum computer.

How surprising would any of these statements be to theoreticians
compared to $P = NP$?

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: This is quite a broad and open ended question..The conjecture that 1. does not happen is the Exponential Time Hypothesis (ETH). The conjecture that 2. does not happen is the Strong Exponential Time Hypothesis (SETH). If you search with these keywords you will find a lot of information about these two. In 4 if the running time of the algorithm is polynomial for p bounded away from 1/2, then you get NP = BPP $\subset$ P\poly which would be quite a surprise and has many consequences, see the Karp-Lipton theorem.  
> **username_0**: @Sasho Nikolov: Interesting. What if in #4, the algorithm is not polynomial for any $p$, but is subexponential for all $0 \le p < 1$?  
> **username_0**: @Ricky Demer: How does "1% NP 'instances in practice'" imply that no OWFs? If the algorithm requires, say, a structured input and the OWF was given a pseudo-random input, like the hash off a crypto hash algorithm, then the algorithm would fail to invert the OWF. Looking it up, it seems that OWFs are defined in terms of random input, so an algorithm that solves for structured inputs would be useless for random ones, and thus couldn't they still be OW by the definition given?  
> **username_2**: @SashoNikolov Consider converting your comment into an answer.  

---

## 0 answers

