News for hackers. Stuff that matters.

A comment on Algorithm Solves Graph Isomorphism in Record Time (2015). Parent comment

Re:Algorithm Solves Graph Isomorphism in Record Time (2015) by repsilat on Friday May 24, 2019 @07:07PM (#20006065)
"Exponential" is often colloquial short-hand for EXPTIME, which is closed under some useful operations (because there's an "any polynomial" in the exponent.)

For one thing, it's robust to reasonable changes of model, for "No true Scotsman" definitions of "reasonable".

[ Parent | on HN ]
Re:Algorithm Solves Graph Isomorphism in Record Time (2015) by mehrdadn on Friday May 24, 2019 @07:12PM (#20006089)
You're talking about closure of EXPTIME under polynomial transformations. You could do similar for quasipolynomial and such; there's nothing about EXPTIME that makes it special in this regard. Edited my comment slightly to hopefully clarify.
[ Parent | on HN ]