Comment by alkyon
18 days ago
It's kind of insulting to the reader that they explain P complexity class without using the word polynomial ("all problems that can be solved in a reasonable amount of time")
18 days ago
It's kind of insulting to the reader that they explain P complexity class without using the word polynomial ("all problems that can be solved in a reasonable amount of time")
Be generous - it saves a lot of time. Once you say "polynomial" readers will think, "like, ANY polynomial, even like n^100?!" and you'll have to explain, yes, but that's STILL better than exponential, etc. They avoided all of that
Quanta targets people who are above average. So I don't think it is too much for them to give a sentence or two stating that. Or even a little graphic could do wonders. I don't think it would take much time or effort to make a graphic like the one on wikipedia[0] and just throw in some equations within the ring. You can easily simplify too, by removing NL and merging EXP. Hell, look at the graphics here[1]. That's much more work.
I don't think Quanta should be afraid of showing math to people. That's really their whole purpose. Even if I think they've made some egregious mistakes that make them untrustable...[2]
[0] https://news.ycombinator.com/item?id=44067043
I suppose my point is that the readers who will wonder about this are a) very likely to know about complexity classes already, or b)capable of learning about it themselves. Perhaps a simple link to something like https://complexityzoo.net/Petting_Zoo would have been a nice middle-ground.
Edit: Aaronson even mentions the n^100 problem in the section about P!
1 reply →
I think this is actually a pretty reasonable description but I also have read Quantum Computing Since Democritus.