[Tainnor]

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.

[zfnmxt]

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

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]

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

[stephencanon]

> (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]

Fair enough, I wasn't aware.

[edanm]

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]

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]

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]

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.

[edanm]

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

I understand why verifying can happen in time P for each machine, but I'm still confused on how you're sure that you hit on the right machine in P time.

For writing Hamlet, you have way more than "P" options for machines, if you're typing at random (I'm not sure how you'd define the input in this case, maybe the length of the work you want them to write?). So even if you can verify in time P, you'll still need to go through way-more-than-P machines before one solves your problem.

Maybe there is a way to use universal search or something to make this happen faster, but I'm not sure how a non-constructive P=NP proof actually gives you the algorithm.

(I tried looking a bit into this and I didn't yet find something that shows otherwise, but I didn't have time to look much.)

[vasili111]

AES is considered quantum resistant.

[Tainnor]

Thanks!