Hey Everyone, Post your solutions to the Mar 15 In-Class Exercise here. Best, Chris

-- Mar 13 In-Class Exercise

For that specific @BT@H(n)@BT@, we are dealing with n strings (as @BT@x <= log(n)@BT@, and there are @BT@2^{|x|}@BT@ possible strings). As we know that @BT@i < log(log(n))@BT@ and @BT@x <= log(n)@BT@, some machine @BT@M_i@BT@ can compute @BT@SAT_H@BT@ in @BT@i*{|x|}^i@BT@ steps. Substituting with the bounds yields @BT@(log(log(n)))*{log(n)}^{log(log(n))}@BT@ steps, which works out to @BT@(log(log(n)))*{2}^{log(log(n))}^2@BT@. We know that @BT@(log(log(n))^2 = o(log(n))@BT@, so we can replace it to be @BT@log(log(n)) * 2^{o(log(n))} = log(log(n)) * n@BT@ Thus, @BT@SAT_H@BT@ can return a result on an input of size @BT@log(n)@BT@ or smaller in time @BT@n*log(log(n))@BT@. As shown at the start, there are @BT@n@BT@ possible strings to test, adding an extra factor of @BT@n@BT@ to the calculation, making our total time @BT@n^2 * log(log(n))@BT@ time, which is within @BT@O(n^3)@BT@.

-- Mar 13 In-Class Exercise

  M = new Turing_Machine(i);

  for(Binary_String s = 0; |s| <= lg(n); s++) {

    //plugs in values from s = linear time
    return M.decideSAT-H(s);

  }

//Sapphire Code for the algorithm (Sapphire is a programming language from another dimension) for(i = 0; i <= lg(lg(n)); ++i) { M = new Turing_Machine(i); for(Binary_String s = 0; |s| <= lg(n); s++) { //plugs in values from s = linear time return M.decideSAT-H(s); } } (runtime is n*lg(n)*lg(lg(n)) < n^3)

-- Mar 13 In-Class Exercise

H(n) = {i} if there exists a machine M_i s.t. 
       for all x belongs to {0,1}^* if |x| < logn then M_i
       decides SAT_H(x) in i|x|^i steps
     = {log log n} otherwise 
 
To find an i that satisfies the first condition, the time required to find would be:
loglogn 2^logn loglogn logn^loglogn
n * loglogn * loglogn * logn^loglogn
n * (loglogn)^2 * logn^loglogn
n * (loglogn)^2 * 2^(loglogn)^2 
 
we can show: (loglogn)^2 = o(logn)
which means we can show that 2^(loglogn)^2 = o(2^logn) i.e. o(n)
so our time bound now becomes: 
 
n * (loglogn)^2 * n
n^2 * logn = O(n^3)

<pre> H(n) = {i} if there exists a machine M_i s.t. for all x belongs to {0,1}^* if |x| < logn then M_i decides SAT_H(x) in i|x|^i steps = {log log n} otherwise To find an i that satisfies the first condition, the time required to find would be: loglogn 2^logn loglogn logn^loglogn n * loglogn * loglogn * logn^loglogn n * (loglogn)^2 * logn^loglogn n * (loglogn)^2 * 2^(loglogn)^2 we can show: (loglogn)^2 = o(logn) which means we can show that 2^(loglogn)^2 = o(2^logn) i.e. o(n) so our time bound now becomes: n * (loglogn)^2 * n n^2 * logn = O(n^3) </pre>

-- Mar 15 In-Class Exercise

We feed inputs of length log(n) to H(n). There are possible 2n inputs upto length n and each of them takes i . |x|^i . So total time require to check satisfiability is n . i . |x|^ i i < log log (n) and x ~ log(n) ~ 2 ^ {log log (n)} substituting, \[ 2n . log log(n) . (log(n))^{log log(n)} \] \[ 2n . log log(n) . (2 ^ {log log (n)})^{log log(n)} \] We know that (log log (n))^2 = o(log(n)) \[ 2n . log log(n) . 2 ^{ log(n)} \] \[ 2n^2 . log log(n) \] this time complexity is smaller than n^3. Hence, \[ H(n) = O(n^3) \] For i machines, we will have log log (n) H(n) time which is < n^3. Hence i * H(n) = O(n^3)

-- Mar 15 In-Class Exercise

  => loglogn * 2n * loglogn*logn^loglogn
  => loglogn * 2n * loglogn*2^(loglogn)*(loglogn)
  => loglogn * 2n * loglogn*2^(loglogn)^2

  => loglogn * 2n * loglogn*2^o(logn)
  => loglogn * 2n * n*loglogn
  => (loglogn)^2 * 2n * n 
  => o(log n) * 2n^2
  => n * 2n^2
  => 2n^3

for each M = M_i we give n strings of length log n, the number of steps taken to check if strings belong to SAT_H we have a function H(n) which runs is i.|x|^i this can be expanded as follows we process strings upto length log n that means we atmost 2n strings => loglogn * 2n * loglogn*logn^loglogn => loglogn * 2n * loglogn*2^(loglogn)*(loglogn) => loglogn * 2n * loglogn*2^(loglogn)^2 We know (loglogn)^2 = o(logn) => loglogn * 2n * loglogn*2^o(logn) => loglogn * 2n * n*loglogn => (loglogn)^2 * 2n * n => o(log n) * 2n^2 => n * 2n^2 => 2n^3 which is equal to O(n^3)

-- Mar 15 In-Class Exercise

	 loglogn otherwise
	 

	=loglogn* 2^logn *loglogn*(logn)^(loglogn)
	=n* (loglogn)^2(logn)^(loglogn)

	logn=2^loglogn
	=n*(loglogn)^2 * 2^(loglogn)^2

	=> 2^(loglogn)^2 < 2^logn
	=> 2^(loglogn)^2 < n
	=n*(loglogn)*n
	=O(n^3)

Hn = i<loglogn if there exists a machine Mi s.t for all x in {0,1}* , if |x| < logn then M decides SATH(X) in i|x|^i steps loglogn otherwise we find i satisfying the above condition starting from i=1 to loglogn since |x|< logn the possible combinations of x is 2^logn Mi can decide SATH(X) in loglogn(logn)^(loglogn) =loglogn* 2^logn *loglogn*(logn)^(loglogn) =n* (loglogn)^2(logn)^(loglogn) wkt n=2^logn logn=2^loglogn =n*(loglogn)^2 * 2^(loglogn)^2 wkt (loglogn)^2 = o(logn) => 2^(loglogn)^2 < 2^logn => 2^(loglogn)^2 < n =n*(loglogn)*n =O(n^3)

-- Mar 15 In-Class Exercise

H(n) = i < log(log(n) if there exists a machine M_i for all x in {0,1}^* if |x| < log(n) then M_i decides SATH(x) in i*|x|^i steps. Otherwise it takes log(log(n)) time. To show the first condition, i*|x|^i = log(log(n))*log(n)^log(log(n)). log(n) = 2^log(log(n)) therefore we have log(log(n))*2^log(log(n))^2 we know that log(log(n))^2 is o(log(n)) which yields log(log(n))*n = O(n^3)