4 ms·
A Short Guide to Hard Problems
- ouid 8y agoIt’s worth mentioning that the discovery of a deterministic polynomial time algorithm to determine primality is pretty recent, 2002. https://en.m.wikipedia.org/wiki/AKS_primality_test https://en.m.wikipedia.org/wiki/AKS_primality_test
- SilasX 8y agoIt's also worth mentioning that AKS didn't have much impact on practical cryptography. The probabilistic algorithms for checking primality are (and were) much faster, and have a tolerably-low chance of failure in selecting prime numbers for crypto. I bring this up because, one (heuristic) reason to believe BPP=P is that, in practice, moving PRIMES from BPP to P didn't make a difference.
- ouid 8y agosomeone (recently?) constructed a composite number which failed miller rabin for 400 iterations or something.
- andreasscherman 8y agoTo help anyone who was as confused as I about this being the first polynomial time algorithm. To me, even the naïve primality test is a polynomial time algorithm over the target number. However, here the AKS primality test is a polynomial time algorithm over the number of digits in the target number, which of course is different!
- allenz 8y agoYes, time complexity is based on the length of the input to a Turing machine. For example, integer factorization is a hard problem because all known algorithms are roughly exponential in the number of bits.
- danharaj 8y ago> This problem is equivalent to the P versus NP problem because if (unexpectedly) P = NP, then all of PH collapses to P (that is, P = PH). It should be noted that the polynomial hierarchy could conceivably collapse at a higher level even if P!=NP. I wouldn't bet on it though.
- crsv 8y agoThis was an interesting read as someone unfamiliar with this space - there were mentions of researcher's trying to prove things about P and it's relationship to other problem classes. Are there any examples of what actual research is being performed or how they're experimenting or trying to tackle these things? Is there practical work involved or is it more about mathematical proof from theory?
- through_17 8y agoWork on determining the relationships between complexity classes is mostly theoretical. I've outlined some of the frontier of this work regarding BPP in another comment. There are two broad classes of exceptions that I know of: * Where this work intersects cryptography: in order for cryptosystems to be secure, we generally have to assume the difficulty of certain specific problems: a complexity assumption! Recent work (see here: https://eprint.iacr.org/2015/907 https://eprint.iacr.org/2015/907) links these assumptions to how easy it is to notice they are false. Intuitively, the easier it is to notice that an assumption is false, the better it is for crypto. A false assumption can be detected and crypto based on this assumption abandoned. * Where computer search is used to assist proofs: A line of work terminating in https://eccc.weizmann.ac.il//report/2011/031/ https://eccc.weizmann.ac.il//report/2011/031/ used computer search to show time-space tradeoffs for solving satisfiability.
- commandlinefan 8y agoThe linked article had an interesting way to phrase the traveling salesman problem. I've always heard it formulated as "given a set of cities and their distances, what is the shortest path that takes the salesman through each city", which wouldn't be NP by the definition given: if you were given the answer, you couldn't check it in polynomial time (unless you could solve the problem in polynomial time).
- dorgo 8y agoI had a problem with this too. But actually the problem can be stated as an NP problem: Compute a round-trip shorter than k. If you have an algorithm to solve the NP version then you can use it to find the shortest round-trip by repeadly applying it to different k-parameters.
- through_17 8y agoThe article lists what we'd like to know, but the research frontiers for each class are also interesting. In each case, how far are we from our objectives? I'll sketch a little bit of the situation for BPP below. Simple constructions using hard decision problems would completely derandomize BPP into P. This is the "hardness to randomness" paradigm: if we could prove that some problem in exponential time was hard enough for circuits, we could completely derandomize BPP. See https://en.wikipedia.org/wiki/Pseudorandom_generator#Pseudorandom_generators_for_derandomization https://en.wikipedia.org/wiki/Pseudorandom_generator#Pseudor... for more information on this approach. Unfortunately, the hardness to randomness program is far from realization. Circuit lower bounds are hard to prove; the best known lower bounds separate NONDETERMINISTIC quasi-polynomial (n^(log n)) time from a circuit class with stringent structural restrictions (no threshold gates, constant depth, polynomial size). See https://eccc.weizmann.ac.il/report/2017/188/ https://eccc.weizmann.ac.il/report/2017/188/ for the state of the art, and https://eccc.weizmann.ac.il//eccc-reports/1994/TR94-010/index.html https://eccc.weizmann.ac.il//eccc-reports/1994/TR94-010/inde... for formal evidence that circuit lower bounds are difficult to prove. On the other hand, if we are willing to accept "average-case" derandomization, we appear closer to BPP "is basically equal to" P. By "average-case" derandomization, I mean that the deterministic version of the algorithm is wrong on some inputs, but it is impossible to sample those inputs efficiently. This is actually another application of the hardness to randomness paradigm: if we knew EXP != BPP, we would obtain an average-case derandomization of BPP into sub-exponential time. This is not quite what we want, of course: it is an open problem to improve that to fully-polynomial time! See https://link.springer.com/article/10.1007%2Fs00037-007-0233-x https://link.springer.com/article/10.1007%2Fs00037-007-0233-... for the state of the art in this approach. Because separations like EXP vs BPP seem easier than circuit lower bounds, (as mentioned in the article, we DO know EXP != P) average-case derandomization seems closer than full derandomization. For the record, EXP contains BPP, because we can just enumerate over all possible random strings, compute the probability of acceptance, and answer accordingly. I don't think the article mentioned this trivial derandomization. So, that's why getting BPP into even sub-exponential time is an interesting result.
- daveguy 8y agoThis seems counter intuitive to me. From the article: >BPP is exactly the same as P, but with the difference that the algorithm is allowed to include steps where its decision-making is randomized. Algorithms in BPP are required only to give the right answer with a probability close to 1. Also from the article: >Computer scientists would like to know whether BPP = P. If that is true, it would mean that every randomized algorithm can be de-randomized. They believe this is the case — that there is an efficient deterministic algorithm for every problem for which there exists an efficient randomized algorithm — but they have not been able to prove it. The reason why I think this seems counter-intuitive: The BPP is only required to give the right answer most of the time (with a probability close to 1). So... A heuristic solution. It seems counter-intuitive that a not-always-correct solution can have a deterministic solution in P. You could get higher and higher probability of the solution repeating N times... So N*O(original). But it seems like that slice of probability that is given up in the heuristic shortcut could be significant... Adding an N multiplier to O(N^2) would still be polynomial but you also still wouldn't be deterministic, just approach deterministic. Maybe I am mixing heuristics and probability where they shouldn't be, or maybe there's a good reason to think the heuristic can always be reformulated to deterministic? Because you can approach the answer with increasing certainty and stay in P? Can someone explain why it is believed BPP = P ?
- through_17 8y agoYes, the article is being a little vague with quantifiers. Let L be a language. L is in BPP if there exist a probabilistic, polynomial time TM such that: For every input x in L, M on x outputs YES with probability close to one. For every input x not in L, M outputs NO with probability close to one. Notice that the input is quantified by "for every" x. The probability in BPP (and thus the error) is only over the random coin tosses that the algorithm uses, not the inputs. This gives our intuition for BPP = P: we can completely eliminate the error using a sufficiently high-quality pseudorandom generator (PRG). We believe that P = BPP because we believe high-quality PRGs exist. More precisely, we can construct such PRGs if there are problems in exponential time that require exponential time even "with advice". Advice is arbitrary information associated with each input length of a problem -- it could even be uncomputable. That is, on all inputs of length n, I get access to a specific string of length poly(n), for instance. That's one string per input length mind, not per input -- if it was per input I could just give you the answer. So such a lower bound is like saying that a certain problem in exponential time is really exponential; there is no strange "compression scheme" that could give us some weird information about all inputs of length n and admit a sub-exponential time solution to the problem. Intuitively, it would be super weird if advice let us cut down on computation time so dramatically. Formally, there are strange consequences if advice is powerful. For instance, if NP is contained in P with polynomial-length advice, PH collapses to the second level (the Karp-Lipton Theorem). On Heuristics: A heuristic is a different notion of complexity: we would instead say for most inputs x, or for any efficiently sample-able distribution over inputs x, the algorithm is correct with high probability. This notion makes perfect sense when combined with deterministic algorithms or with randomized algorithms. In the deterministic setting, the probability is only over the inputs. In the randomized setting, we have a joint probability over inputs and tossed coins.