4 ms·

Open Problems in Theoretical Computer Science

78 points by p4bl0 11y ago

danharaj 11y ago
Open problems in Homotopy Type Theory: https://ncatlab.org/homotopytypetheory/show/open+problems https://ncatlab.org/homotopytypetheory/show/open+problems
crb002 11y ago
#1 What is the complexity of boolean matrix multiplication? #2 Is there a parallel algorithm for GCD?
Ace17 11y ago
Fun fact: the problems are a lot more hard to understand if you're browsing with Javascript disabled.
- a3_nm 11y ago
  Sorry about this, it should now be fixed, and I submitted it upstream: https://github.com/mitya57/python-markdown-math/pull/10 https://github.com/mitya57/python-markdown-math/pull/10 Thanks for reporting!
Animats 11y ago
One of the big problems is to find a lower bound on some cryptographic algorithm. We think that factoring is hard, but there is no proof of this. The knapsack problem, used in the first public key system, was thought to be hard, but isn't.
- _asummers 11y ago
  My understanding is that factoring is NOT believed to be NP-hard. Can you point to literature that suggests it is? Researchers and professors I've spoken to seem to think it lacks the inherent structure that many NP-complete problems seem to have. My (nonexpert) personal belief is that it will be one of the next problems to fall.
  - kirrent 11y ago
    Factoring is almost certainly not NP-hard. That would mean that NP is contained in BQP which would be a staggering result. While there are some NP problems that are in BQP the idea that somehow NP-complete problems are solvable in polynomial time on a quantum computer seems kinda ridiculous to me. I'd be happy to be proven wrong some time in the future though.
- abetusk 11y ago
  The knapsack problem is hard (it's NP-Complete, which is what most people mean when they say "it's hard") but the candidate encryption scheme based off of the knapsack problem turned out to be easily breakable (by using lattice reduction techniques, if I remember correctly)[1]. They had to put in structure to the knapsack encoding (to be able to, for example, encrypt and decrypt messages)[2] but put "too much" [3] in so that things like lattice reduction could find solutions without too much trouble (read polynomial time). [1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.7624&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.... [2] https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac... [3] https://en.wikipedia.org/wiki/Superincreasing_sequence https://en.wikipedia.org/wiki/Superincreasing_sequence
- hannob 11y ago
  This is basically a followup-problem of P vs. NP. If you can't show that P!=NP then all attempts to prove the security of a public key crypto algorithm are pointless. Or in other words: The science of provable lower bounds of crypto systems will only start once you solve one of the biggest unsolved problems in mathematics and theoretical computer science. All we have today (and likely for a very long time) is problems we think are hard.
a3_nm 11y ago
Author here, thanks for the comments! I added two problems to http://a3nm.net/work/research/questions/#well-known-conjectures http://a3nm.net/work/research/questions/#well-known-conjectu... following ideas here.
- chaoxu 11y ago
  I have just answered one of those problems here. http://cstheory.stackexchange.com/questions/20245/subset-of-a-bipartite-graph-with-maximal-number-of-minimal-unmatched-vertices http://cstheory.stackexchange.com/questions/20245/subset-of-... I hope I didn't misunderstood the problem.
  - a3_nm 11y ago
    Thanks a lot! I think you understood the problem correctly, I checked your argument and it seems correct to me, see https://cstheory.stackexchange.com/questions/20245/subset-of-a-bipartite-graph-with-maximal-number-of-minimal-unmatched-vertices#comment77255_33603 https://cstheory.stackexchange.com/questions/20245/subset-of... We have no specific plans for this result but it's always comforting to have an answer after all and know that it's in P. Plus this way I learnt about the existence of submodular functions. :) List updated (http://a3nm.net/work/research/questions/#complexity-of-an-assignment-problem-with-subsets http://a3nm.net/work/research/questions/#complexity-of-an-as...). Thanks again for making me remove the first problem from this list!
    - chaoxu 11y ago
      np. There might be ways to speed up the running time for this special case. Naive algorithm using submodular minization + maximum matching as an oracle would take around O(n^c) where c is probably more than 10.

78 points by p4bl0 11y ago

Open problems in Homotopy Type Theory: https://ncatlab.org/homotopytypetheory/show/open+problems https://ncatlab.org/homotopytypetheory/show/open+problems

crb002 11y ago

#1 What is the complexity of boolean matrix multiplication? #2 Is there a parallel algorithm for GCD?

Ace17 11y ago

Fun fact: the problems are a lot more hard to understand if you're browsing with Javascript disabled.

a3_nm 11y ago
Sorry about this, it should now be fixed, and I submitted it upstream: https://github.com/mitya57/python-markdown-math/pull/10 https://github.com/mitya57/python-markdown-math/pull/10 Thanks for reporting!

Animats 11y ago

One of the big problems is to find a lower bound on some cryptographic algorithm. We think that factoring is hard, but there is no proof of this. The knapsack problem, used in the first public key system, was thought to be hard, but isn't.

_asummers 11y ago
My understanding is that factoring is NOT believed to be NP-hard. Can you point to literature that suggests it is? Researchers and professors I've spoken to seem to think it lacks the inherent structure that many NP-complete problems seem to have. My (nonexpert) personal belief is that it will be one of the next problems to fall.
- kirrent 11y ago
  Factoring is almost certainly not NP-hard. That would mean that NP is contained in BQP which would be a staggering result. While there are some NP problems that are in BQP the idea that somehow NP-complete problems are solvable in polynomial time on a quantum computer seems kinda ridiculous to me. I'd be happy to be proven wrong some time in the future though.
abetusk 11y ago
The knapsack problem is hard (it's NP-Complete, which is what most people mean when they say "it's hard") but the candidate encryption scheme based off of the knapsack problem turned out to be easily breakable (by using lattice reduction techniques, if I remember correctly)[1]. They had to put in structure to the knapsack encoding (to be able to, for example, encrypt and decrypt messages)[2] but put "too much" [3] in so that things like lattice reduction could find solutions without too much trouble (read polynomial time). [1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.7624&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.... [2] https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac... [3] https://en.wikipedia.org/wiki/Superincreasing_sequence https://en.wikipedia.org/wiki/Superincreasing_sequence
hannob 11y ago
This is basically a followup-problem of P vs. NP. If you can't show that P!=NP then all attempts to prove the security of a public key crypto algorithm are pointless. Or in other words: The science of provable lower bounds of crypto systems will only start once you solve one of the biggest unsolved problems in mathematics and theoretical computer science. All we have today (and likely for a very long time) is problems we think are hard.

a3_nm 11y ago

Author here, thanks for the comments! I added two problems to http://a3nm.net/work/research/questions/#well-known-conjectures http://a3nm.net/work/research/questions/#well-known-conjectu... following ideas here.

chaoxu 11y ago
I have just answered one of those problems here. http://cstheory.stackexchange.com/questions/20245/subset-of-a-bipartite-graph-with-maximal-number-of-minimal-unmatched-vertices http://cstheory.stackexchange.com/questions/20245/subset-of-... I hope I didn't misunderstood the problem.
- a3_nm 11y ago
  Thanks a lot! I think you understood the problem correctly, I checked your argument and it seems correct to me, see https://cstheory.stackexchange.com/questions/20245/subset-of-a-bipartite-graph-with-maximal-number-of-minimal-unmatched-vertices#comment77255_33603 https://cstheory.stackexchange.com/questions/20245/subset-of... We have no specific plans for this result but it's always comforting to have an answer after all and know that it's in P. Plus this way I learnt about the existence of submodular functions. :) List updated (http://a3nm.net/work/research/questions/#complexity-of-an-assignment-problem-with-subsets http://a3nm.net/work/research/questions/#complexity-of-an-as...). Thanks again for making me remove the first problem from this list!
  - chaoxu 11y ago
    np. There might be ways to speed up the running time for this special case. Naive algorithm using submodular minization + maximum matching as an oracle would take around O(n^c) where c is probably more than 10.