KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
I was talking with a student the other day about the common complexity classes of algorithms, like O(n), O(n k ), O(n lg n), O(2 n ), O(n!), etc. I was trying to come up with an example of a problem for which solutions whose best known runtime is super-exponential, such as O(2 2 n ), but still decidable (e.g. not the halting problem!) The only example I know of is satisfiability of Presburger arithmetic , which I don't think any intro CS students would really understand or be able to relate to. My question is whether there is a well-known problem whose best known solution has runtime that is superexponential; at least ω(n!) or ω(n n ). I would really hope that there is some "reasonable" problem meeting this description, but I'm not aware of any.
Tags (comma-separated)
Save Edits
Cancel