This is an example of an assignment question, there are 3 of them so I created my own in order to better understand it.

First, we have the variable m which is a binary encoding such as 100#001#010 which is translated to [4, 1, 2]

Next is the variable n = the total length of the input/encoding

And k which is the largest number in the list (4 in the previous list)

Now we set $f(n)$ as the turing machine that took m as input, and want to see if $f(n) = O(g(n))$ where $g(n)$ is a polynomial.

How can I solve this on $f(n) = m (log (n)) (log (k))$?

  • $\begingroup$ I'm sorry but your question doesn't make any sense to me. What do you mean by "set $f(n)$-TM"? What is $f$? What do you mean by "solve this"? $\endgroup$ – David Richerby Mar 15 '19 at 15:34
  • 1
    $\begingroup$ Is your underlying question something like "I have a Turing machine and I've calculated its running time in a way that isn't purely in terms of the length of the input. The running time I calculated depends on the value of some of the numbers in the input, as well as its length. How can I tell if the running time is bounded by some polynomial function of the input's length?" $\endgroup$ – David Richerby Mar 15 '19 at 15:35
  • $\begingroup$ @DavidRicherby I clarified further, this is as much information as was given, but your phrasing makes a lot of sense. $\endgroup$ – Andrew Raleigh Mar 15 '19 at 15:41
  • 1
    $\begingroup$ @ZeroUltimax Absolutely not! Consider the input 111#1, which has $k=7>5=n$. $\endgroup$ – David Richerby Mar 15 '19 at 16:01
  • 1
    $\begingroup$ @David Richerby Correct, I misread the definition of k as the number of digits. In the above case, with k being the largest number, it would be log_2(k) < n. Since k < 2^n $\endgroup$ – ZeroUltimax Mar 15 '19 at 18:24

Your question is rather unclear but I think it's something like this:

I have a Turing machine and I want to figure out if it runs in polynomial time. That means that its running time must be bounded by a polynomial function of the input's length. I've figured out an expression for its running time but this expression is in terms of, e.g., some of the numbers represented in the input, and not just the input's length. How do I proceed from here?

So you've computed a running time that's something like $f(n, x_1, x_2, ...)$ where the $n$ is the input length and the $x_i$ are other quantities associated with the input. What you need to do is bound how big those quantities in terms of $n$ and then substitute those bounds into&nbsp:$f$, to obtain a function whose only input is $n$.

For example, your input includes a list of numbers. That list could have as many as roughly $n/2$ entries, since it could be $0\#0\#0\#\ldots$. If the list has just one entry, that number has roughly $n$ bits, so the biggest number in the list could be as big as $2^n$ or so.

In other situations, you might know more about the input. Perhaps the entries in the list all have to be different. Then the input can't be $0\#0\#0\#\dots$ and the entries themselves have to get longer than just one bit. If you had $k$ entries in the list, they'd need about $\log k$ bits each, at a minimum, so you'd have $k\log k\leq n$, which you can try to solve and use.

Then, substitute everything you get into $f$ and see what you get. For the example you have in your question, it's something like $|m|=\Theta(n)$, $k=\Theta(2^n)$, so $|m|(\log n)(\log k)$ is about $n(\log n)(\log 2^n) = n^2\log n$.

| cite | improve this answer | |
  • $\begingroup$ That makes a lot of sense! So in the case of $n^2 log (m)$ it would be $n^2 log(n)$ since $log(m)$ is equivalent to $n$? $\endgroup$ – Andrew Raleigh Mar 15 '19 at 17:33
  • 1
    $\begingroup$ Yes, except that you mean "$\log m$ is equivalent to $\log n$", or "$m$ is equivalent to $n$" -- I assume that was just a typo/brainfart $\endgroup$ – David Richerby Mar 15 '19 at 17:35
  • $\begingroup$ Yeah it was, thanks for the help. In questions similar to this I should try to equate variables such as $m$ / $k$ and the like to $n$ to find the $c$ in $O(g(n))$ if I'm picking it up correctly? $\endgroup$ – Andrew Raleigh Mar 15 '19 at 17:38
  • 1
    $\begingroup$ Yeah, something like that. Though you'll usually be equating them to some function of $n$, and usually bounding rather than equating. But, yes, that's the general technique. $\endgroup$ – David Richerby Mar 15 '19 at 17:44
  • 1
    $\begingroup$ Correct. If your algorithm had running time $\Theta(k)$, that would be $\Theta(2^n)$. An example of this is the simple primality test where you try to determine if a number $k$ is prime by trying to divide it by each integer $2, 3, \dots, \sqrt{k}$. This takes at least $\sqrt{k}$ divisions and, even if you could do each division in constant time (which is to say, I'm too lazy to look up how long they actually take!), this takes time at least $\sqrt{k}\approx \sqrt{2^n}=2^{n/2}$. $\endgroup$ – David Richerby Mar 15 '19 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.