user21816
Reputation
258
Next privilege 300 Rep.
Create new tags
 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?