Timeline for Groups where word problem is solvable, but not quickly?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 29, 2016 at 18:19 | history | edited | YCor | CC BY-SA 3.0 |
edited body
|
| Dec 29, 2016 at 17:50 | comment | added | YCor | By the way, assuming it's classical, I'd be curious of references about hardness of the membership problem of recursive subsets of integers. Is it true that for every recursive function $f(n)$, there exists a recursive set of positive integers such that for every algorithm solving membership to $A$, the supremum $g(n)$ of halting times for all inputs $k\le n$ satisfies $g(n) \gg f(n)$? | |
| Dec 29, 2016 at 17:47 | history | answered | YCor | CC BY-SA 3.0 |