On Tue, Jun 18, 2024, 5:10 PM John Rose <johnr...@polyplexic.com> wrote:
> It helps to know this: > > https://www.quantamagazine.org/in-highly-connected-networks-theres-always-a-loop-20240607/ > > Proof: > https://arxiv.org/abs/2402.06603 > I give up. What are the implications? The Hamiltonian circuit problem is NP complete and is closely related to the traveling salesman problem that UPS has to solve to plan optimal delivery routes. Instead they find solutions that are good enough. The paper proves that highly connected graphs in a certain sense have Hamiltonian paths, something we already suspected empirically. I don't think the paper brings us any closer to solving the P vs NP problem. The implication of P = NP would be all cryptography is broken except for one time pad. Bitcoin would drop to $0. Password hashes could be easily cracked and Wifi, SSH, and HTTPS connections easily tapped. Digital signatures could be easily forged. To break any encryption using a known plaintext attack, construct a logic circuit implementing ciphertext = encrypt(plaintext, key), and then set the key bits one at a time and ask a SAT solver if there is a solution with the remaining key bits. SAT is NP complete. The implication of P ≠ NP is not much because we already believe it is true because lots of people have tried and failed to find fast solutions to any of the over 3000 known NP complete problems. ------------------------------------------ Artificial General Intelligence List: AGI Permalink: https://agi.topicbox.com/groups/agi/T482783e118fee37e-M2e2cb4411a17d330e9349114 Delivery options: https://agi.topicbox.com/groups/agi/subscription
