4
$\begingroup$

If I may summarize how I feel about collapse of the polynomial hierarchy:

willie hears ya

Are intractable models of computation, including collapse of $\mathbf{PH}$ or $\mathbf{PSPACE}$ above but not down to $\mathbf P$ useful for any reason besides the off chance they might collapse? Obviously "useful" is broad - I would gladly be interested in answers outside of computer science, but I am wondering if their study helps us understand really anything besides them themselves.

I am taking complexity theory and have essentially been wondering this entire semester, if my increasingly fluency in problems of the form $\exists\forall\exists\forall...$

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ What makes you think that P is relevant in practice at all? $\endgroup$ – Raphael♦ Dec 18 '16 at 21:35
  • $\begingroup$ "I would gladly be interested in answers outside of computer science" -- so why are you here? $\endgroup$ – Raphael♦ Dec 18 '16 at 21:35
  • $\begingroup$ @Raphael Are either of those questions serious? I'm here to learn about computer science. That includes learning about applications of computer science. $\endgroup$ – djechlin Dec 18 '16 at 22:41
  • $\begingroup$ And why do you think that computer scientists can give you "answers outside of computer science"? I suggest you make up your mind which kind of answers you want and then pick the correct place to ask for them. $\endgroup$ – Raphael♦ Dec 19 '16 at 8:32
  • $\begingroup$ @Raphael To answer your question seriously even though you're acting like a troll: 1. academic research is often interdisciplinary. 2. research is frequently motivated by results in other fields that demand technical machinery be introduced. 3. researchers are often aware of applications of their research and even enjoy learning about them. $\endgroup$ – djechlin Dec 19 '16 at 17:21
3
$\begingroup$

Not all problems that are encountered in an industrial setting are clearly either NP-Complete or else polynomial-time solvable, even with randomness, heuristics and approximation. So if you encounter (a variant of) a problem such as Exact Independent Set, or Succinct Graph Diameter, for example, then you ought to be looking to the complexity classes $\text{DP}$ and $\Sigma_2^P$. Without the study of these classes, there is no proper placement of these problems, no way to relate them to one another and therefore no way to tackle them coherently, and no way to quantify their hardness. We might look for a way to compactly store and then sell the solutions to NP-Complete problems after we've brute forced them for many inputs. But because of Karp and Lipton, we know that this is impossible, unless the polynomial hierarchy collapses to the second level. In general, these conditional collapses are great for question of the form "Can I...", "No.".

I would love to provide an answer like "We were struggling, but then Immerman and Szelepcsényi proved that $\text{Nondeterministic Logspace}$ was closed under complement, and that really gave a boost to our startup!", being a student myself I don't have any anecdotal evidence, and I would love to hear from someone more seasoned.

So if you are looking for an industrial application of computational complexity theory beyond SAT Solvers, then you may be disappointed. Complexity theory is to computer science a bit like string theory is to physics; it is purely theoretical and its study is not motivated by the urge to solve a particular problem, but rather to understand the nature of computation - how do randomness and nonuniform computation relate to one another? Do all programs with small memory footprints have a fast implementation? - very much like the motivation of theoretical physics is not to design a slightly more efficient engine, but rather to understand the laws of physics. You are taking a theoretical class, and must not be surprised to learn about theoretical results. There are coding classes where you come from; if you prefer those, take those.

If I take the liberty of venturing into speculation, then you may know that right now we do not even know how to rule out ridiculous scenarios in which $\text{BPP}=\text{NEXP}$. Of course everyone believes that the result will be $\text{BPP}\subsetneq\text{NEXP}$, but a proof of this fact cannot come without major advances in our understanding of computation, and, staying with the metaphor of physics, where major advances in our understanding of fundamental physics invariably spurs major progress in unexpected areas, I feel confident in saying that these results, when they come, will spur major progress across all fields of computing.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Approximation algorithms actually fit the bill of an answer to my question. There is a dialog between, "establish that this problem is quite hard, now weaken or specialize it and repose the question." $\endgroup$ – djechlin Dec 18 '16 at 18:09
  • $\begingroup$ Industry would be quite interesting -- other areas of math, c.s., statistics, etc. would be interesting as well. A positive result in ML or comp. learning theory would be interesting as well. $\endgroup$ – djechlin Dec 18 '16 at 18:09
  • 1
    $\begingroup$ Personally I don't believe that the resolution of major conjectures in complexity theory will be practically relevant. Regarding Reingold's result, from a practical point of view it is completely spurious, since randomized algorithms for SL were already known. $\endgroup$ – Yuval Filmus Dec 18 '16 at 19:42
  • 1
    $\begingroup$ lol, BPP = NEXP. $\endgroup$ – djechlin Dec 19 '16 at 19:32
  • 1
    $\begingroup$ @LieuweVinkhuijzen Theoretical computer science has been demonstrating its irrelevance to practice for a few decades now. A nice example is fast matrix multiplication, where all progress since Strassen's algorithm is purely theoretical. Another good example is machine learning – while supposedly theory was important for the design of SVMs, it is completely helpless in regard to neural networks and their recent successes. Complexity theory is even farther removed from practice. A question like P vs BPP is practically useless, since we do have access to randomness. That's just one example. $\endgroup$ – Yuval Filmus Dec 19 '16 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.