Open Problems in Theoretical Computer Science | Hacker News Reader

Open Problems in Theoretical Computer Science

a3nm.net

78 pointsp4bl013 comments

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

#1 What is the complexity of boolean matrix multiplication?

#2 Is there a parallel algorithm for GCD?

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

I have just answered one of those problems here. http://cstheory.stackexchange.com/questions/20245/subset-of-... I hope I didn't misunderstood the problem.

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...

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-as...). Thanks again for making me remove the first problem from this list!

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.

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

Sorry about this, it should now be fixed, and I submitted it upstream: https://github.com/mitya57/python-markdown-math/pull/10

Thanks for reporting!

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.

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.

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.

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....

[2] https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...

[3] https://en.wikipedia.org/wiki/Superincreasing_sequence

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.

Reply on news.ycombinator.com