Timeline for Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 14, 2013 at 16:30 | comment | added | vzn | and speaking of the time hiearchy thm, this observation is related. define $f(n)$ as in the original question. then there exists a language that can be recognized in $O\left( f(n) \over {\log n} \right)$ but not in $O\left( f(n) \over (\log n)^2 \right)$ for all (time constructible) $f(n)$ such that $f(n) \over (\log n)^2$ is $\omega(n)$. | |
| Feb 13, 2013 at 17:43 | comment | added | vzn | new/fixed/similar idea, let $f(n)=e^{\log n}$ and then a DTIME($f(n)$) language exists that is not recognizable in DTIME$\left( e^{\log n} \over \log n \right)$. | |
| Feb 13, 2013 at 16:28 | comment | added | vzn | fyi wikipedia says that $f(n)$ in the time hierarchy thm need only by time constructible & then gives two defns of time constructible. at the end, "No function which is o(n) can be time-constructible unless it is eventually constant, since there is insufficient time to read the entire input." so maybe this all amts to some undergraduate exercise or test question... heres another idea, what if the length of the input is specified in binary at the beginning of the input? | |
| Feb 13, 2013 at 14:12 | comment | added | Emil Jeřábek | @JɛffE: You cannot test “Are the first $n/\lg n$ bits of the input all zeros?” in $O(n/\log n)$ time on a TM, since you do not know what $n$ is without first reading the whole input, which takes time $n$. It is a standard fact that if $f(n)<n$, then $\mathrm{DTIME}(f(n))$ contains only languages the membership in which can be determined from the first $k$ bits of input for a constant $k$ (and therefore are computable in constant time). | |
| Feb 13, 2013 at 3:53 | comment | added | vzn | hi guys after further study admit/concede its not so simple & something is not quite right with the above idea based on other formulations of the time hierarchy theorem other than wikipedia, which doesnt make it clear theres a lower bound on languages where it is applicable, and the other formulations make the restriction more clear eg here. however, suspect there might exist some language with complexity that approaches (but still exceeds) a linear bound "from above" for which the above idea fits...."exercise for reader" =) | |
| Feb 13, 2013 at 2:18 | comment | added | Sasho Nikolov | @JɛffE Fair enough, I was lazy to be more careful in my statement. The issue is that a "hierarchy" is trivial once you reach sublinear DTIME. I.e. $\mathsf{DTIME}(f(n))$ for $f(n) = o(n)$ is very easily seen to be a strict subset of $\mathsf{DTIME}(n)$. Take "is the $n$-th bit of the input 1?" | |
| Feb 13, 2013 at 2:06 | comment | added | Jeffε | No, @SashoNikolov, $\mathsf{DTIME}(n/\log n)$ is not trivial. Compare "Are the first $n/\lg n$ bits of the input all zeros?" with "Do the first $n/\lg n$ bits of the input encode a satisfiable boolean formula?" | |
| Feb 13, 2013 at 0:21 | comment | added | Sasho Nikolov | sublinear algorithms make sense in oracle & random access models. DTIME is standardly defined w.r.t. multitape TM, and that's the definition used in the hierarchy theorem for DTIME. | |
| Feb 12, 2013 at 4:51 | comment | added | vzn | ?? there is still theory for sublinear time algorithms... | |
| Feb 12, 2013 at 4:23 | comment | added | Sasho Nikolov | on a TM, $\mathsf{DTIME}(n/\log n)$ is trivial as it doesn't allow the machine to read the whole input. also, the DTIME notation makes the big-oh notation unnecessary. | |
| Feb 12, 2013 at 2:13 | history | edited | vzn | CC BY-SA 3.0 |
fix the wording
|
| Feb 12, 2013 at 2:08 | history | edited | vzn | CC BY-SA 3.0 |
fix the wording
|
| Feb 12, 2013 at 1:05 | history | edited | vzn | CC BY-SA 3.0 |
"thinking outside the box"
|
| Feb 12, 2013 at 0:59 | history | edited | vzn | CC BY-SA 3.0 |
fix it with substitution
|
| Feb 12, 2013 at 0:53 | history | answered | vzn | CC BY-SA 3.0 |