Impact
~7k
people reached
- 0 posts edited
- 0 helpful flags
- 9 votes cast
Mar
11 |
awarded | Popular Question |
Sep
24 |
awarded | Autobiographer |
Sep
8 |
awarded | Popular Question |
Jul
2 |
awarded | Curious |
Jun
19 |
accepted | Can we efficiently compute a third Nash Equilibrium, given two? |
Jun
19 |
comment |
What new primitive recursive functions are needed to reconcile Turing time complexity with Gödel time complexity?
@JoelDavidHamkins: I want the following statement to be true -- For every function $f(|n|)$ and for every recursive function, there exists a recursive definition that is $O(f(|n|))$ in Godel complexity if and only if there exists a Turing machine that computes the function in $O(f(|n|))$ steps. I am not restricting my attention to Turing machines of a particular notation alphabet -- If there is a recursive definition in $O(|n|)$ then I'd like some Turing machine of any input alphabet that runs in $O(|n|)$ steps. |
Jun
19 |
comment |
What new primitive recursive functions are needed to reconcile Turing time complexity with Gödel time complexity?
Yes, by "best-case" I mean "optimal worst-case," thank you. By "equal to," I mean "asymptotically equal to" - I would like it such that (for example) if a function can be implemented in $O(|n|)$ time on a Turing machine, then it can necessarily be implemented in $O(|n|)$ time via primitive recursive functions (and vice versa). |
Jun
19 |
asked | What new primitive recursive functions are needed to reconcile Turing time complexity with Gödel time complexity? |
Apr
27 |
awarded | Commentator |
Apr
27 |
comment |
When does the finite union of convex sets have a hole in it?
Man, that is a cool answer you linked to. I do have a way to test intersections, so that will do perfectly. |
Apr
27 |
revised |
When does the finite union of convex sets have a hole in it?
edited title |
Apr
27 |
revised |
When does the finite union of convex sets have a hole in it?
added 299 characters in body |
Apr
27 |
comment |
When does the finite union of convex sets have a hole in it?
1. Yes, it's the union, not the intersection of the sets (the intersection would be convex =) ). 2. Yes, I am attempting a floating-point algorithm. Rather than place restrictions on the sets, I'm hoping to use standard convex optimization techniques as a subroutine (the $\epsilon$-fudginess in these techniques is okay; I'd be fine with an algorithm that reports "the functions come within $\epsilon$ of being hole-less"). |
Apr
27 |
revised |
When does the finite union of convex sets have a hole in it?
deleted 16 characters in body; edited title; added 55 characters in body |
Apr
27 |
asked | When does the finite union of convex sets have a hole in it? |
Mar
1 |
awarded | Yearling |
Feb
5 |
asked | Geometric interpretations of matrix inverses |
Jan
23 |
accepted | Does this result exist in the literature? |
Jan
22 |
asked | Does this result exist in the literature? |
Jan
8 |
asked | Is there a general process for conditioning a stochastic process above a boundary? |