# Tagged Questions

28 views

### Asymptotic relation between these two functions

I have two functions $f(n) = (log n)^{100}$ $g(n) = n^{0.1}$ What is the relationship between these two functions. According to me it should be f(n) = ω(g(n) because the rate of growth of f(n) is ...
54 views

### Dynamic programming algorithm for GCD?

I can't seem to find a clear answer on this. I'm inclined to believe that there is not a DP solution for GCD, given the lack of information so far in my searches on the subject. I suppose that in ...
6 views

### Determining if a Language is contained in P, based on two representations of max runtime

Is the language L1 = {(M, w, 1^t) | M accepts w after running for max t steps} contained in the class P? I know that there are 2 main goals: runs in polynomial ...
61 views

### Prove that $6^{\sqrt n} = O({n \choose n/2})$

Prove that $6^{\sqrt n} = O({n \choose n/2})$ I was able to show that prove that $6^{\sqrt n} = O({n \choose n/2})$ with defining $n=2k$ and $a_k= \frac {k!^26^\sqrt k} {2k!}$ and then show ...
51 views

### prove\disprove - there are functions $f(n)$ and $g(n)$ such that $g(n) = o(1)$ and $f(n-g(n)) \neq \Theta((f(n))$

there are functions $f(n)$ and $g(n)$ such that $g(n) = o(1)$ and $f(n-g(n)) \neq \Theta((f(n))$ Thought about $f(n) = |sin(n)|,\ g(n)= \frac1n$ then $f(n-g(n))= |sin(n-\frac1n)|$ and then for any ...
56 views

### Primitive recursive and Turing machines

Can someone give me a hint or the start of a possible proof for the following theorem: A function $f: \mathbb{N}^r \rightarrow \mathbb{N}$ is primitive recursive if and only if there is a ...
16 views

164 views

### Sorting Algorithm analysis on a list of 0 and 1 element.

I'm trying to understand the difference would it make if following sorting algorithms are given a set of binary inputs i.e. collection of 0 and 1's only. a) Heapsort b) Quicksort c) MergeSort d) ...
129 views

### Sum in tree nodes - algorithm

I've got one very hard problem. Given a tree with nodes with integers. We need to find the largest sum of label values for a set of nodes which does not include any adjacent pair of nodes. ...
88 views

### Determining position at some point in time

I try to solve the following problem. On $n$ parallel railway tracks $n$ trains are going with constant speeds $v_1$, $v_2$, . . . , $v_n$. At time $t$ = 0 the trains are at positions $k_1$, ...
386 views

### Form or asymptotic behaviour of $T(n) =2T(n-1)+n$

$T(n) =$ if $n=1$, then time execution is $1$, if $n \geq 2$ then $2T(n-1)+n$ The options are: $T(n) = 2^{n+1} - n - 2$ $T(n) = O(n2^n)$ $T(n) = \Omega(n)$ $T(n) = \theta(2^n)$ Thanks.
62 views

### Time to resolve a problem of size $1000$ in one second, how time take resolve the same problem of size $10.000$ in $n^2$?

A algorithm require one second to resolve a problem of size $1000$ a local machine. How long time take the same algorithm to resolve the same problem for a problem size of $10.000$ if the algorithm ...
134 views

### 2-Player Game PSpace-Completeness

So there is a n x n game board and each location on the board has an integer. Player one picks a number from row 1 and player 2 picks a number from row 2 and they alternate until there are no more ...
260 views

### NP-Completeness of Certain Bounded Degree Graphs

I was studying time complexity when it comes to bounded degree graph problems and I was wondering if I can get help with the following two problems. 1) L = set of all (G, k) where G is a graph with ...
476 views

### P or NP-Complete? (concerning 2-CNF formulas)

I have two languages that I want to either prove is in P or NP-complete. 1) 2-CNF formulas where there exists an assignment that satisfies the 3/4 of the first 1000 clauses and all of the rest. 2) ...
138 views

### Fast inversion of a triangular matrix

I need to inverse a matrix $A$ given its $QR$ decomposition. It's a numerical task. It is told that the inversion should be "possibly cheap". But it does not look like I can do something more ...
101 views

### Assuming that SAT is decidable in $2^{O(\sqrt{n})}$, is every language in NP decidable in $2^{O(\sqrt{n})}$?

Assuming that we have an algorithm that decides SAT in $2^{O(\sqrt{n})}$, can every language in NP be decided in that time? I had the following idea: Because SAT is NP-complete, every language in NP ...
969 views

### Is coNP closed under Kleene star?

Is coNP closed under Kleene star operation? I have the answers, in which they say it is possible to build a graph that describes all possible divisions of the string in which the sub-words are in in ...
234 views

### Finding a Big-O notation of: $\sum\limits_{i=1}^{k} ( t(a_i n)) + n$

I'm trying to find a Big-O notation of: $\displaystyle\sum_{i=1}^{k} ( t(a_in)) + n$, where $\displaystyle\sum_{i=1}^{k} (a_i) < 1$ using a recursion tree method and substitution method. I've ...
235 views

### Proving that basic linear algebra problems (LINEQ and Linear Programming) are in NP

I'm working through the problems in Arora & Barak's textbook on Computational Complexity. It's all been good so far, but I'm kind of stuck on this pair of problems in Chapter 2 (2.3 and 2.4). I'm ...
Let $M$ consist of the words in $\{0,1\}^{*}$, such that the number of $1$'s in $w$ is exactly $\lceil \log(n) \rceil$, where $n = |w|$. a) Design a sequence of circuits $C_n$ recognizing $M$. $C_n$ ...