Are there any counterintuitive results in theoretical computer science? Some math and logic paradoxes could be automatically applied to computers probably, but are there any paradoxes that were discovered in computer science itself?

By paradoxes I mean counter intuitive results that look like a contradiction.
I find the fact that network flow is polynomial time counter intuitive. It is seems much harder on first look than many NP-Hard problems. Or putting it differently, there are many results in CS where the running time to solve them is way better than what you would expect it to be.