Timeline for What is the difference between NP=EXP and ETH, and what does the community believe about their truth?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 18 at 16:25 | comment | added | rus9384 | @user56834 Yes, E-hard under linear time reductions, I should have specified. | |
| Jun 18 at 15:36 | comment | added | user56834 | @rus9384, so by E-hard in this context you mean there is a linear time reduction? | |
| Jun 18 at 14:18 | comment | added | rus9384 | @user56834 "if a problem is EXP-hard, it's also E-hard" Under polynomial time reductions, yes. Not under linear time reductions, though. A problem solvable in time $\Theta(2^n)$ has a quadratic (but not quicker) time reduction to a problem solvable in time $\Theta(2^{\sqrt n})$. So, SAT (at least as it currently stands) can be EXP-hard and yet be solvable in time $o(2^n)$. | |
| Jun 18 at 13:49 | comment | added | user56834 | @rus9384, how is that possible? It holds thst $E\subset EXP$, right? so then if a problem is EXP-hard, it's also E-hard. Hence if we have an EXP-complete problem that can be solved in $2^{\sqrt n}$, then you can solve E problems in that time too, by reducing them to the EXP complete problem. what is wrog with my argument? | |
| Jun 16 at 21:12 | comment | added | rus9384 | @user56834 E is a class of languages decidable in time $2^{O(n)}$, whereas EXP is a class of languages decidable in time $2^{poly(n)}$. E-complete problems can't be solved in time $2^{o(n)}$, e.g. $2^{\sqrt n}$, whereas some EXP-complete problems can. | |
| Jun 15 at 15:26 | comment | added | user56834 | What is the difference between NP=E and NP=EXP? | |
| Jun 15 at 14:32 | comment | added | rus9384 | NP=E implies ETH, because: 1)Every E-complete problem requires $\Omega(a^n)$ for some constant $a>1$ time to solve. 2) There is a polynomial time reduction from an EXP-complete problem to 3-SAT, which means 3-SAT requires at least exponential time to solve (otherwise the reduction would violate the point 1). As for NP=EXP, it could be still the case that e.g. 3- SAT is solvable in time $O(2^{\sqrt n})$. | |
| Jun 15 at 11:29 | comment | added | nicolas duek | Yes, you are correct there. Regarding your realization this is not exactly the reason why the equality is not obtained. Think of it in this way: there might be harder problems in EXP than 3-SAT, such that even if you allow yourself to solve them in 3-SAT's complexity, it still wouldn't be enough. Thus, those problems are not in NP. Regarding your second statement - no, it doesn't imply either. This wouldn't give you any new information about 3-SAT, as you already know it's in NP and thus also in EXP. | |
| Jun 15 at 11:07 | comment | added | user56834 | does NP=EXPTIME at least imply ETH? | |
| Jun 15 at 11:02 | comment | added | user56834 | but 3-SAT is NP, so therefore there is a polynomial time reduction from 3-SAT to any NP-hard problem. therefore if 3-SAT requires exponential time, so do all NP-hard problems. Am I at least coreect here? I guess I kind of assumed that "all NP hard problems take exponential time" implies NP=EXP, but I realise now that that isn't obvious, because there still might be exptime problems that cannot be polynomially checked. | |
| S Jun 15 at 9:25 | review | First answers | |||
| Jun 16 at 10:04 | |||||
| S Jun 15 at 9:25 | history | answered | nicolas duek | CC BY-SA 4.0 |