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