4
$\begingroup$

While CS theorists pursue the beauty and unity of their mathematical theories, their results can have a practical and industrial impact.

As we know, P versus NP is often talked about with its relation to public crypto. systems. Moreover, streaming algorithms often directly lead to industrial benefits.

Is there any possible research direction that would satisfy the following conditions?

(1)Solving problems in this area of TCS would lead to a fundamental change in our society.

(2)It would be required to understand other academic subjects (such as physics or electronics) to solve problems related to this TCS field.

I am afraid that this question is not appropriate for this stack exchange, but please forgive me if it is.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ (2) is not clear. also keep in mind many algorithms have already had huge impact. AI & related areas (eg datamining) are big potential areas but its not always considered part of TCS(.se) ie maybe more applied $\endgroup$
    – vzn
    Commented Oct 9, 2012 at 17:16

4 Answers 4

Reset to default
2
$\begingroup$

Just like quantum-computing, I suppose DNA-computing throws in a significantly different physical model of computing (ability to self-replicate). In principle that should stimulate significant cross research between theory and practice.

Another potential area is Goemetric Complexity Theory. At this point, of course it is probably the most abstruse area, and no one knows how the final shape will look like. But as Ketan Mulmuley had pointed out in one of his talks (I'll update the reference if I can find it) - that any success of GCT (or any P/NP separation work for that matter) will actually result in establishing the significant largeness of the class P - i.e., to successfully show complexity class separation and avoid Razborov-Rudich-type (or Aaronson-Wigderson-type ) barriers at the same time, one needs algorithms to solve problems for which at present only doubly or triply exponential solutions are known at best. If polynomial time algorithms are discovered, that could be a potential game-changer in many applied areas as well.

Improve this answer
$\endgroup$
13
$\begingroup$

There are many examples of theoretical research that had a big impact on society, e.g., the RSA cryptosystem, the algorithm behind Google search, the algorithmic ideas behind Akamai, etc. But the thing with basic research is that it's hard to know in advance what's going to be influential, when and how.

One potential candidate could be quantum computing, which has strong ties to both physics and electronics, and could make a huge difference (allowing efficient simulations of quantum systems, breaking RSA, and more). However, it's hard to know when quantum computers will be built (if at all).

Improve this answer
$\endgroup$
1
  • $\begingroup$ One thing that always fascinated me, is the fact that just like mathematics has huge implications in understanding the laws of nature ( for physicists to judge what nature may or may not allow), someday some of the TCS results may have similar implications. The P/NP question, the parallel repition theorem, etc., may have already made such implications. But then, TCS, albeit studied in different departments in most universities, is probably just another branch of mathematics anyway. $\endgroup$
    – Arnab
    Commented Oct 10, 2012 at 22:36
5
$\begingroup$

Fields such as bioinformatics and computational biology could fundamentally change the way we live since it may lead to revolutions in drugs manufacturing, disease prevention and treatment, and possibly synthetic biology. Currently, there is no formal language in TCS that explains how DNA code controls the functions of biological systems. There is no theory in TCS that determines the functions of some DNA segment. Research progress in those fields would have huge impact on medicine, biology and therefore society.

Improve this answer
$\endgroup$
1
  • $\begingroup$ closely related, protein folding problem, mainly a physics simulation problem but with ties to TCS $\endgroup$
    – vzn
    Commented Oct 9, 2012 at 17:17
4
$\begingroup$

Another field that started out in TCS is formal verification. Two very theoretical and important results in the field are: Pnueli's paper on linear temporal logic (LTL) from 77 and Vardi and Wolper LTL to Buchi automata construction from the 80s. In the 90s, McMillan suggested to use BDDs in order to work with huge systems, and from that point the industry started using formal verification regularly. Now it's being used mainly in hardware, and there is much research on developing tools for software as well.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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