4 ms·

I thought it was helpful. Got a better link?

alberto_ol 4y ago
This article for non-specialists is longer and more technical, but I found it interesting: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AW09/AW09.pdf https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AW09/AW0...
photochemsyn 4y ago
This looks good: https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf > "Although there’s no “purely mechanical procedure” to determine if a mathematical statement S is true or false, there is a mechanical procedure to determine if S has a proof of some bounded length n: simply enumerate over all proofs of length at most n, and check if any of them prove S. This method, however, takes exponential time. The P ? = NP problem asks whether there’s a fast algorithm to find such a proof (or to report that no proof of length at most n exists), for a suitable meaning of the word “fast.”" "Fast" seems to mean polynomial time (which can still be a very long time, but not blowing up in the way that exponential time does). The paper gives some clear examples: > "Think of a large jigsaw puzzle with (say) 10^1000 possible ways of arranging the pieces, or an encrypted message with a similarly huge number of possible decrypts, or an airline with astronomically many ways of scheduling its flights, or a neural network with millions of weights that can be set independently. All of these examples share two key features: (1) a finite but exponentially-large space of possible solutions; and (2) a fast, mechanical way to check whether any claimed solution is “valid.” (For example, do the puzzle pieces now fit together in a rectangle? Does the proposed airline schedule achieve the desired profit? Does the neural network correctly classify the images in a test suite?) > "We’re asking whether, under the above conditions, there’s a general method to find a valid solution whenever one exists, and which is enormously faster than just trying all the possibilities one by one, from now till the end of the universe, like in Jorge Luis Borges’ Library of Babel." The paper also discusses caveats, assumptions, limitations, etc. of the concept in an approachable manner. Then it goes off into the depths of theorem and conjecture.

This article for non-specialists is longer and more technical, but I found it interesting: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AW09/AW09.pdf https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AW09/AW0...

photochemsyn 4y ago

This looks good: https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf > "Although there’s no “purely mechanical procedure” to determine if a mathematical statement S is true or false, there is a mechanical procedure to determine if S has a proof of some bounded length n: simply enumerate over all proofs of length at most n, and check if any of them prove S. This method, however, takes exponential time. The P ? = NP problem asks whether there’s a fast algorithm to find such a proof (or to report that no proof of length at most n exists), for a suitable meaning of the word “fast.”" "Fast" seems to mean polynomial time (which can still be a very long time, but not blowing up in the way that exponential time does). The paper gives some clear examples: > "Think of a large jigsaw puzzle with (say) 10^1000 possible ways of arranging the pieces, or an encrypted message with a similarly huge number of possible decrypts, or an airline with astronomically many ways of scheduling its flights, or a neural network with millions of weights that can be set independently. All of these examples share two key features: (1) a finite but exponentially-large space of possible solutions; and (2) a fast, mechanical way to check whether any claimed solution is “valid.” (For example, do the puzzle pieces now fit together in a rectangle? Does the proposed airline schedule achieve the desired profit? Does the neural network correctly classify the images in a test suite?) > "We’re asking whether, under the above conditions, there’s a general method to find a valid solution whenever one exists, and which is enormously faster than just trying all the possibilities one by one, from now till the end of the universe, like in Jorge Luis Borges’ Library of Babel." The paper also discusses caveats, assumptions, limitations, etc. of the concept in an approachable manner. Then it goes off into the depths of theorem and conjecture.