A few days ago I saw a news that caught my attention, about the Exponential Time Hypotesis (ETH) and its connection to 3-SAT: apparently an AI has proved it false! This reminded me two things: that I almost forgot everything I know about this topic and that I had promised myself to complete the section… Continue reading P, NP, NC and Other Funny Complexity Classes
Tag: computer science
Computational Models
Computers are very fast circuits able to do several basic logical, mathematical and memory operations and we use long sequences of these operations to perform almost every possible task. They are so fast that we think the elaboration as instantaneous, but if the input is large it may require some time. I still remember the… Continue reading Computational Models