Timeline for Hard-to-compute real numbers
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 27, 2018 at 17:17 | comment | added | Alex Mennen | Problems that take exponential time to compute aren't hard enough to be good examples. Because to compute a number to precision $2^{-n}$, you need to compute all the first $n$ bits, not just the $n$th bit. This will already take exponential time if the bits are given by an easy computational problem, and if the bits are given by a problem that takes exponential time, then computing the first $n$ of them takes... still exponential time. To get a number that is hard to compute, you need to use a decision problem that cannot be solved in exponential time. | |
| Oct 22, 2016 at 22:56 | comment | added | Timothy Chow | @Lembik : If you want a computational problem for which all the bits are (believed to be) hard to compute, try a cryptographic problem. Anyway, the point is that the whole business about real numbers is a red herring. The question reduces to, "Do there exist hard computational problems?" The answer is yes. | |
| Oct 22, 2016 at 14:36 | comment | added | Wojowu | @Lembik It is true for nearly every "natural" decision problem that there are some instances where the problem is easy. This is even true for halting problem - there are a lot of machines for which we easily see whether they halt or not (let me also mention this paper). You are also right this depends on the ordering - we can define an ordering such that odd-numbered graphs have cycles and even-numbered ones don't. It is necessary for us to specify that the ordering is "simpler" than the problem at hand, so to say. This is usually meant implicitly. | |
| Oct 22, 2016 at 14:32 | comment | added | Wojowu | @MohammadAl-Turkistany I'm afraid you are right. But I feel like the point is not so much about the specific example of Hamiltonian graph. You can replace it with any problem known to not be in P. | |
| Oct 22, 2016 at 10:42 | comment | added | Mohammad Al-Turkistany | Isn't this conditional on $P \ne NP$? (If $P=NP$ then Hamiltonian cycle is in $P$ ). | |
| Oct 22, 2016 at 8:17 | comment | added | Simd | For this formulation we have no idea which bits are hard to compute it seems. Could it be that almost all of them are easy ? In fact if we compute the bits in order and the graphs are suitably ordered, could all the bits be easy to compute? | |
| Oct 22, 2016 at 3:14 | history | answered | Timothy Chow | CC BY-SA 3.0 |