You can achieve constant amortized time per operation by keeping a dynamically-sized array $A$ (using the doubling/halving technique). To insert an element append it at the end. To implement ...

If a problem is NP-Hard it means that there exists a class of instances of that problem whose are NP-Hard. It is perfectly possible for other specific classes of instances to be solvable in polynomial ...

The language is regular and a possible regular expression for $L$ is $(a\mid b)^* (a \mid b) (a \mid b)^* = (a \mid b)^+$.

You don't need to first write all 3-tuples and then check, for each of them, whether it induces a triangle. You can just enumerate the 3-tuples one at a time and reject as soon as you find one that ...

If by convert you mean reduce (through a Karp-reduction), then it is possible to reduce any problem $A$ in $P$ to any non-trivial problem $B$ in $P$. Here "non trivial" means that $B$ has at least ...

You can prove the claim by induction on $n$. If $n=1$ the claim is clearly true since it suffices to start from the unique "+1" node. When $n > 1$, let $u$ and $v$ be two consecutive ...

If $n$ is fixed then $a^n$ is just a single word and so is $a^nb^n$. If by $a^n$ you mean the language $\{a^n \mid n \ge 0\}$ (whose corresponding regular expression is $a^*$) then the problem is that ...

I understand the question as asking for the truth value of the proposition $\exists A \in \mathsf{NP}, \forall B \in \mathsf{NP}, A \not\le_p B$, where $\le_p$ denotes Karp reducibility. Then the ...

A generalization of this class of problems is widely studied. See, e.g., this paper for a survey. In your particular case, the problem can be easily solved without any asymptotic change in the ...

In order for $f(O(n)) \in O(f(n))$ to hold you essentially want $f$ to satisfy $f(cn) \le df(n)$ where $n$ is sufficiently large. Here the inequality must hold for all sufficiently large constants $c$,...

Each element $j$ contributes $1$ to the cardinality of all sets $\{j > i \mid \sigma_j > i\}$ for which $i < \min\{\sigma_j, j\}$, and $0$ to the other sets. You can compute all $n$ values $K(... View answer 8 votes I see several problems. In your first part you say that, given a regular language$L$,$\overline{L}$is regular since$\Sigma^*- L$is also regular. This is true, but it is implicitly using the ... View answer Accepted answer 7 votes Let$v$be a vertex of the tree. If$\pi_v$is the path from the root of the tree to$v$, then the string$s(v)$constructed from the labels of$\pi_v$is unique (if you really want, you can prove ... View answer Accepted answer 7 votes For$i \ge 0$define$w_i = b^i aa$. For any$i,j \ge 0$with$i \neq j$you have that$b^i$is a distinguishing extension for$w_i$and$w_j$. Indeed,$w_i b^i \not\in L_2$but$w_jb^i \in L_2$. Then ... View answer Accepted answer 7 votes The first definition you are referring to is probably the one that defines$\mathsf{NP}$as the set of problems$\Pi$for which there exist a non-deterministic poly-time Turing machine that decides$\...

Assuming $n$ is a power of $2$, you have: $$\sum_{i=0}^{\log n} \log \frac{n}{2^i} = \sum_{i=0}^{\log n} \left( \log n - i \right) = \sum_{i=0}^{\log n} i = \frac{(\log n)(\log n+1)}{2} = \Theta(\log^... View answer 6 votes The measure you are trying to minimize is called (directed) bandwidth. Finding a minimum directed bandwidth ordering is NP-hard. View answer Accepted answer 6 votes Turing Machines can simulate binary search, in the sense that they can compute whatever you can compute using binary search. You seem to be confusing computability and complexity, which are two ... View answer 6 votes It is false that$$ \sum_{n=0}^\infty \frac{n^2}{2^n} \ge \left( \sum_{n=0}^\infty n^2 \right) \cdot \left( \sum_{n=0}^\infty \frac{1}{2^n} \right), $$assuming that's what you meant. You can see ... View answer Accepted answer 6 votes Your analysis of the time complexity is wrong. Specifically this statement: In every loop we have less n s-clique where every s-clique might have maximum s(n−1) adjacent nodes to look at. In fact ... View answer Accepted answer 6 votes Assuming arithmetic operations take constant time, you can compute it in O(\log \log n) time. Start with n_0=2 and iteratively compute n_i = n_{i-1} \cdot n_{i-1} = 2^{2^i} until n_{i} > n... View answer 6 votes There is no polynomial-time algorithm for your problem, unless \mathsf{P}=\mathsf{NP}. Let H be a connected undirected graph with at least 2 vertices and consider the directed graph G ... View answer Accepted answer 6 votes Using  <  with the big-oh notation is a bit of abuse of notation. Formally, I take your statement to mean \forall f(n) \in O(n^{\log n}), \; f(n) \in O((\log n)^n). Let f(n) \in O(n^{\log n})... View answer 6 votes You can define two kinds of Turing Machines, transducers and acceptors. Acceptors have two final states (accept and reject) while transducers have only one final state and are used to calculate ... View answer 5 votes They are two different definitions. The interview definition calls a safe edge one that is not part of any cycle and therefore cannot be removed from G without disconnecting it, thus changing the ... View answer Accepted answer 5 votes The argument looks correct. Also notice that you can get a better (but still loose) upper bound as follows:$$ \binom{k}{p-1} \le \sum_{i=0}^{k} \binom{k}{i} = 2^k  Where the equality $\sum_{i=0}^{k}... View answer 5 votes A polynomial-time reduction only needs to preserve the size of the problem up to a polynomial upper bound (which is implied by the time constraint). As an example, suppose you have two NP-complete ... View answer Accepted answer 5 votes Let$B^*, B_1, B_2, \dots, B_{2n-2}$be the the bins sorted by the number of white balls, in non-increasing order (break ties arbitrarily). Notice that the first bin is called$B^*$. Consider the two ... View answer Accepted answer 5 votes Membership of your problem in$\mathsf{NP}$is trivial. To prove that it is also$\mathsf{NP}$-hard consider an instance of (the decision version of) independent set consisting of a graph$G=(V, E)\$ ...