The success of neural networks on problems like Go and protein folding, long considered intractable NP-hard problems, is profound. It suggests our formal understanding of computational hardness, which focuses on worst-case scenarios, may be an incomplete model for how to find useful, approximate solutions in practice.

P represents problems we can solve, while NP represents problems where a solution can be easily verified. If P=NP, any problem with a verifiable solution could be efficiently solved, implying we can know everything we want to know. It's a question about the ultimate limits of discovery.

The brain's hardware limitations, like slow and stochastic neurons, may actually be advantages. These properties seem perfectly suited for probabilistic inference algorithms that rely on sampling—a task that requires explicit, computationally-intensive random number generation in digital systems. Hardware and algorithm are likely co-designed.

Zero-knowledge proofs are universal for any problem in NP (any problem with a verifiable proof). The method involves reducing the original problem to an NP-complete problem like graph 3-coloring. By proving knowledge of the graph coloring without revealing it, one indirectly proves the original theorem without revealing its substance.

In algorithm design, randomness isn't free. High-quality random bits (from quantum sources) are expensive, while cheaper sources (thermal noise) have lower quality. This reframes randomness as a resource to be managed and minimized, just like time or space complexity.

The theory of randomness extraction provides methods to take a long string of bits from a weak source (e.g., weather data) and distill it into a shorter string of nearly perfect, uniformly random bits. This is crucial for using real-world physical phenomena as a viable source for cryptographic applications.

The Riemann Hypothesis aligns with the model that primes are pseudo-random. If proven false, it would imply a deep, undiscovered pattern in their distribution. This 'secret patent' to the primes would shatter the foundations of cryptography, as any hidden structure could lead to an exploit.

While problems like protein folding are NP-hard in theory, the instances found in nature have structural properties that allow for efficient solutions. Real-world cases of NP-hard problems aren't the adversarial, worst-case scenarios used in complexity proofs, explaining the gap between theory and practice.

For some NP-hard problems, like 3-SAT, a random guess satisfies 7/8ths of clauses. The PCP theorem proves that finding a solution satisfying just an epsilon more (7/8 + ε) is as computationally hard as finding a perfect 100% solution. This places severe limits on approximation algorithms.