4 ms·

Theoretical CS fundamentals are not going to change. Practically, that means among other things: - Unless somebody finds a polynomial algorithm for an NP-compl

Theoretical CS fundamentals are not going to change. Practically, that means among other things: - Unless somebody finds a polynomial algorithm for an NP-complete problem (which is a taller order than just proving P=NP), several interesting problems will continue to be infeasible to solve exactly in the general case with large data. - If, in addition, quantum computers don't prove to be viable, commonly used cryptosystems such as RSA, AES, ECC, will probably continue to be secure provided they're used correctly. - Results like the Two Generals Problem, the CAP theorem, etc. will still make distributed systems difficult to work with and require tradeoffs. - Rice's theorem, that it is impossible to determine computational properties of arbitrary programs, will still apply, making static analysis (including antivirus programs, security scans, etc.) heuristic rather than exact. - etc.

vasili111 3y ago
AES is considered quantum resistant.
- Tainnor 3y ago
  Thanks!
stephencanon 3y ago
> (which is a taller order than just proving P=NP) A proof that P=NP immediately gives a polynomial-time algorithm for NP complete problems via universal search. It’s so wildly impractical as to probably not change anything, but it _is_ in P.
- Tainnor 3y ago
  Fair enough, I wasn't aware.
- edanm 3y ago
  What? That doesn't seem correct to me. (Since I'm not actually that fluent in CS complexity theory, I assume the problem is my understanding.) Can you explain more about what universal search is, and/or where I can read about how it would solve the problem?
  - stephencanon 3y ago
    The handwavy explanation is you can enumerate a list of all the turing machines. You run the first one for one step, then you run the first two for two steps, then the first three for three steps, etc, until one of them halts. If P=NP, this will happen in polynomial time, which gives you the algorithm you need.
    - edanm 3y ago
      I'm not sure I understand. How would a list of all Turing machines possibly help when trying to solve a specific problem in P time? Are they built in a way that is relevant to the problem you're trying to solve (if so, how?).
      - zfnmxt 3y ago
        Disclaimer: I didn't know about universal search until I read stephencanon's comment. I just thought it was fun to think about and I think the answer is what follows, but it could be wrong! Imagine your problem is to write Hamlet by Shakespeare. One way to write Hamlet by Shakespeare is to enlist many monkeys who then type at random (but with the property that no two monkeys type the same thing). Each monkey also has a special "done" button that they press when they're done writing. Some monkeys never press it and write forever. So you instruct each monkey to type one key and then you check each monkey to see if they pressed "done". If they pressed "done", you check if they wrote Hamlet. Otherwise, you continue and have the monkeys each press another key. Since there are infinitely many different monkeys, so you can't enlist them all at once, because then checking after each key press would take you infinitely long! This is why you play that game with at the first step you enlist one monkey, then two, then three, etc; it ensures at each step there are finitely many monkeys to check. Of all the possible monkeys, one monkey will write Hamlet exactly and then press "done". This scheme finds that monkey. Similarly, for Turing machines, there will be at least one (technically, infinitely many) that solves your problem. You just have to figure out which one it is by doing the enumeration that stephencanon detailed. If P = NP, that enumeration process can happen in P time. Keep in mind that all problems in NP have polynomial time verifiers. So you can always check a solution (i.e., checking if the monkey actually wrote Hamlet) in polynomial time.
zfnmxt 3y ago
> - Rice's theorem, that it is impossible to determine computational properties of arbitrary programs, will still apply, making static analysis (including antivirus programs, security scans, etc.) heuristic rather than exact. I think this is misleading. There are many exact static analyses---proof-checking in theorem provers like Coq is an exact static analysis. More generally, type checking can be an exact static analysis that guarantees semantic properties of your programs, like termination. If you can force your programs to be in a certain form (e.g., statically rejecting type incorrect programs), you can sufficiently restrict the class of programs (Turing machines) that you're considering that you can indeed determine non-trivial computational properties of your programs.
- Tainnor 3y ago
  I was very careful to specify "computational properties" (as opposed to things like program length or side effects) and "arbitrary programs" (with "arbitrary" meaning that it doesn't suffice to prove individual programs correct, and "program" meaning that I'm not talking about single functions). I should probably have been more specific by writing "decide" instead of "determine", because you can absolutely 'determine' a computational property as long as you're willing to ignore false negatives. For example, it's easy enough to write a termination checker by just checking for loops and equivalent constructs (or e.g. in Idris, by requiring that all functions are total), but that will of course reject a large number of programs that do in fact terminate. Coq is not a Turing Complete language, so Rice's theorem doesn't apply. But almost all people are not writing programs in Coq. I think static types are great, but they don't contradict any of this.
  - zfnmxt 3y ago
    > but they don't contradict any of this. Sure, and I agree with what you've said. But as you pointed out, you have to be very particular/exact with language with these things. I just wanted to emphasize that there are many constrained settings (but still practical) where Rice's theorem doesn't apply.

vasili111 3y ago

AES is considered quantum resistant.

Tainnor 3y ago
Thanks!

stephencanon 3y ago

> (which is a taller order than just proving P=NP) A proof that P=NP immediately gives a polynomial-time algorithm for NP complete problems via universal search. It’s so wildly impractical as to probably not change anything, but it _is_ in P.

Tainnor 3y ago
Fair enough, I wasn't aware.
edanm 3y ago
What? That doesn't seem correct to me. (Since I'm not actually that fluent in CS complexity theory, I assume the problem is my understanding.) Can you explain more about what universal search is, and/or where I can read about how it would solve the problem?
- stephencanon 3y ago
  The handwavy explanation is you can enumerate a list of all the turing machines. You run the first one for one step, then you run the first two for two steps, then the first three for three steps, etc, until one of them halts. If P=NP, this will happen in polynomial time, which gives you the algorithm you need.
  - edanm 3y ago
    I'm not sure I understand. How would a list of all Turing machines possibly help when trying to solve a specific problem in P time? Are they built in a way that is relevant to the problem you're trying to solve (if so, how?).
    - zfnmxt 3y ago
      Disclaimer: I didn't know about universal search until I read stephencanon's comment. I just thought it was fun to think about and I think the answer is what follows, but it could be wrong! Imagine your problem is to write Hamlet by Shakespeare. One way to write Hamlet by Shakespeare is to enlist many monkeys who then type at random (but with the property that no two monkeys type the same thing). Each monkey also has a special "done" button that they press when they're done writing. Some monkeys never press it and write forever. So you instruct each monkey to type one key and then you check each monkey to see if they pressed "done". If they pressed "done", you check if they wrote Hamlet. Otherwise, you continue and have the monkeys each press another key. Since there are infinitely many different monkeys, so you can't enlist them all at once, because then checking after each key press would take you infinitely long! This is why you play that game with at the first step you enlist one monkey, then two, then three, etc; it ensures at each step there are finitely many monkeys to check. Of all the possible monkeys, one monkey will write Hamlet exactly and then press "done". This scheme finds that monkey. Similarly, for Turing machines, there will be at least one (technically, infinitely many) that solves your problem. You just have to figure out which one it is by doing the enumeration that stephencanon detailed. If P = NP, that enumeration process can happen in P time. Keep in mind that all problems in NP have polynomial time verifiers. So you can always check a solution (i.e., checking if the monkey actually wrote Hamlet) in polynomial time.

zfnmxt 3y ago

> - Rice's theorem, that it is impossible to determine computational properties of arbitrary programs, will still apply, making static analysis (including antivirus programs, security scans, etc.) heuristic rather than exact. I think this is misleading. There are many exact static analyses---proof-checking in theorem provers like Coq is an exact static analysis. More generally, type checking can be an exact static analysis that guarantees semantic properties of your programs, like termination. If you can force your programs to be in a certain form (e.g., statically rejecting type incorrect programs), you can sufficiently restrict the class of programs (Turing machines) that you're considering that you can indeed determine non-trivial computational properties of your programs.

Tainnor 3y ago
I was very careful to specify "computational properties" (as opposed to things like program length or side effects) and "arbitrary programs" (with "arbitrary" meaning that it doesn't suffice to prove individual programs correct, and "program" meaning that I'm not talking about single functions). I should probably have been more specific by writing "decide" instead of "determine", because you can absolutely 'determine' a computational property as long as you're willing to ignore false negatives. For example, it's easy enough to write a termination checker by just checking for loops and equivalent constructs (or e.g. in Idris, by requiring that all functions are total), but that will of course reject a large number of programs that do in fact terminate. Coq is not a Turing Complete language, so Rice's theorem doesn't apply. But almost all people are not writing programs in Coq. I think static types are great, but they don't contradict any of this.
- zfnmxt 3y ago
  > but they don't contradict any of this. Sure, and I agree with what you've said. But as you pointed out, you have to be very particular/exact with language with these things. I just wanted to emphasize that there are many constrained settings (but still practical) where Rice's theorem doesn't apply.