logoalt Hacker News

adrianNtoday at 2:45 AM0 repliesview on HN

We actually understand quite a bit about the universe and the kinds of computers we can build. People also think about computers in speculative physics scenarios, eg closed timelike curves can be used to solve pspace complete problems.

I don’t think you can plausibly argue that complexity theory‘s base assumptions are a bad choice, at least not in the sense that you would assume that you can build exponentially more powerful computers in the physical universe. In fact, concerns about energy densities, limited amounts of matter, and the speed of light make it more difficult than typical machine models assume.