# Tag Info

0

Denote an interval with $(i, j)$, meaning it is the interval from $a[i]$ to $a[j]$. Denote by $OR(i, j)$ the value $a[i]$ or $a[i+1] \ldots a[j]$. For each $k$, we want to find $i$ that maximizes (or minimize) $OR(i, i+k-1)$. For each $i$, consider the set $\{OR(i, j) | j \le i\}$ (that is, all the possible different values of intervals starting at position ...

2

The notation $\{0,1\}^*$ refers to the space of finite strings in the alphabet $\{0,1\}$, including the empty string.

1

If the linear systems are solved by Gaussian elimination, then each step takes $O(d^3)$ time. The number of steps needed depends on the convergence rate. In the case of a simple root, this rate is quadratic. Much of the time, we can do better than the algorithm suggested above. For instance you can use an iterative method to solve the linear systems ...

0

UNARY-CLIQUE∈NPC V = "On input ((G, 0^k), c), where G= (V, E) is an undirected graph, 2≤k≤|V| and c is a set of nodes: 1. Test whether c is a set of k nodes in G. 2. Test whether G contains all edges connecting nodes in c. 3. If both pass, accept; otherwise, reject." We showed a poly-time verifier, therefore UNARY-CLIQUE∈NP. Reduction from CLIQUE: Given ...

1

Let me first treat part one, since this is the easiest part Part 1: the number of subsets of a given set $X$ is $2^{|X|}-1$, where $|X|$ is the number of elements in $X$. I had to substract the $1$ because you are not interested in the empty subset $\emptyset$. A way to see why this is the number of options is the following: consider a set of $|X|$ slots, ...

2

Actually, UNARY-CLIQUE is in $P$. Remember that the input length of UNARY-CLIQUE grows linearly in $k$ while the input length of CLIQUE only grows logarithmically. The naive approach of "for all $k$-element subsets of $V$, check if the set is a clique" is actually polynomial in $k$ and thus polynomial in the input length. For the normal CLIQUE, it's still ...

0

The fastest known algorithms are based on the Bailey-Borwein-Plouffe formula. A particular variation later developed by Plouffe (see here) can be used to calculate the base-$10$ digits of $\pi$ by using the formula $$\pi + 3 = \sum_{n=1}^{\infty} \frac{n 2^n n!^2}{(2n)!}$$ Plouffe's method calculates the $n^{\text{th}}$ digit of $\pi$ in ...

1

It is easiest to see the differences using an example, so consider the geometric series $\sum_{k=1}^{j}{ar^{k-1}}$ with initial value $a$ and common ratio $r$. To find the nth term evaluate the summand $ar^{k-1}$ when $k = n$. 1st term = $ar^{1-1} = ar^0 = a$ 2nd term = $ar^{2-1} = ar^1 = ar$ (n-1)th term = $ar^{(n-1)-1} = ar^{n-2}$ nth term = ...

1

Hint: You can reduce the problem to 2-CNF-SAT. Have clauses such as $B_{17}\lor R_{17}$, $\neg B_{17} \lor \neg R_{17}$, and $\neg B_{17}\lor \neg B_{42}$.

1

Any turn-based game like chess can be viewed as a tree, where the root node is the starting position, each possible move for the first player is an arc from the root to another node, then all arcs from nodes in the second layer to positions in the third layer are initial moves for the second player, and so on. The leaf nodes at the bottom of the tree are ...

0

With a computer program you can do the following: The program can go through all the possible moves, all possible reactions of the human, all possible counter-reactions and so on... Now each possible move can be scored by an heuristic. The program can do the move with the best expected outcome... The program can look in a database of all recorded chess ...

2

If you're proficeint with double-digit mental arithmetic then it can be done mentally as follows. $3233 = 3249-16 = 57^2\!-4^2 = 53\cdot 61.\,$ Repeated squaring mod $61$ and $53$ we find ${\rm mod}\ 61\!:\,\ 42\equiv -19 \overset{x^2}\to\color{#c00}{ -5}\overset{x^2}\to 25\overset{x^2}\to 15\overset{x^2}\to -19,\$ i.e. $\ 42^{16}\equiv -19,\,$ therefore ...

0

i have this here $$42^5\equiv 440 \mod 3233$$ and $$42^{10}=(42^{5})^2\equiv 2853 \mod 3233$$ and then we use that $$42^7\equiv 240 \mod 3233$$ then we get the searched result.

2

There are ways to calculate it, modulo is remainder counting basically. $$7 = 2 \mod 5$$ because $7=5*1+2$ $$12 = 2 \mod 5$$ because $12=5*2+2$ and so on, so if you want to calculate for example $73 = a \mod 7$ you can do this, that is want to get $a$, take 73 and continue subtracting 7 until you no longer can. $73-7=66$, $66-7=59$ etc until we get $10-7=3$ ...

3

When you see "modulo", especially if you are using a calculator, think of it as the remainder term when you do division. For example, $10 \mod 5 = 0$, because $5|10$, but $7\mod 5 = 2$ since $7 = 5 +2$. The reason your calculator says $113 \mod 120 = 113$ is because $113<120$, so it isn't doing any division. More generally, the idea is that two numbers ...

0

By definition $\text{NPC}\subseteq \text{NP}$. To show the other inclusion, $\text{NP}\subseteq \text{NPC}$, formally we need to find a way to transform any instance of a problem $A\in\text{NP}$ to an instance of any other problem $B\in\text{NP}$ in polynomial time, and transform the solution of the instance of $B$ to a solution of $A$. But the whole point ...

2

NPC is the set of all NP problems which would let you solve any other NP problem in polynomial time. If P = NP, then you can already solve any NP problem in polynomial time, so all NP problems are NP-complete.

1

If you write $T(n)$ for the number of comparisons needed for finding a fixed element $x$ in a sorted list of $n$ elements (in the worst case), you get $T(0)=0$, $T(1)=1$; and you also can get a recurrence relation of the form $$T(n)=T\left(\left\lceil \frac{n}{2}\right\rceil\right)+1$$ (can you see why? The $+1$ is the comparison of $x$ with the median ...

3

To reconcile this with the general case, note that each block matrix addition adds two matrices of dimension $\frac{n}{2} \times \frac{n}{2}$, so of $\frac{n^2}{4}$ elements, which is the complexity claimed (as constants don't matter). In your case, it happens to be that $$4 = n = \frac{n^2}{4} = \frac{16}{4} = 4$$ Generally, though, be careful with ...

4

$AE$ and $BG$ are each submatrices of size $\frac{1}{2}n \times \frac{1}{2}n$. Hence, each submatrix has $\frac{1}{4}n^2$ entries. Thus, $AE + BG$ requires $\frac{1}{4}n^2 \in \mathcal O(n^2)$ additions. The problem in your small example is that half of $4$, then squared, coincidentally equals $4$.

5

Your matrix is a $2 \times 2$ matrix, which has $2^2=4$ entries. In your example your $n=2$ and $n^2 = 4$. Adding two $n \times n$ matrices (which have $n^2$ entries) scale as $\mathcal{O}(n^2)$, since you would need to add $n^2$ entries of the first matrix with the $n^2$ entries of the second matrix.

2

I'm going to assume the number is exactly $poly(n)$. The proof certificate for $L^C$ is the list of all words of length $n$ which are in $L$ with their proof certificates. To check whether $x \not\in L$ against the proof certificate, first check that the number of strings in the certificate is exactly $poly(n)$, then for each string in the certificate check ...

0

You have that $$\binom{n}{k} = \frac{n!}{(n-k)!k!} = \frac{1}{k!}\frac{n!}{(n-k)!} = \frac{1}{k!}\left(n(n-1)(n-2)\dots(n-k+1)\right).$$ As far as the $\Theta(\cdot)$ notation is concerned, $k$ is a constant, so $\frac{1}{k!}=\Theta(1)$, and $$\left(n(n-1)(n-2)\dots(n-k+1)\right) = ... 1 Assuming positive integral powers, then k\geq1, hence 1-k\leq0, so that$$1+n^{m(1-k)}\leq2 for sufficiently large $n$.

0

(This answer is wrong but by virtue of apnortons comment below it might yet prove instructional to someone else but me) I'm a bit in doubt after reading the authorative answer by apnorton, but it seems to me the NP-completeness of (is-not-Hamiltonian) can still be proven. For this one would need to a) show that (is-not-Hamiltonian) is in NP and b) find a ...

2

You probably know that showing a graph is Hamiltonian is an NP-complete problem. Thus, showing that a graph is not Hamiltonian is a co-NP-complete problem. It is an open problem as to whether or not a co-NP-complete problem can also be NP-complete. So, the short answer is, "we don't know yet!"

2

No, this cannot be concluded. What you are describing is not a strict restriction of the problem. I will give a counter example. Suppose you have a problem $A$ that takes an input $n$ that characterizes a two variable function $f$, and that outputs $(x,y)$ such that $f(x,y)$ is of maximal value. Further suppose that a problem $B_c$ does the same thing for a ...

-1

Yes. In general if a restricted version of a problem is NP-hard then the unrestricted version must be as well since it contains the restricted version as a special case. NP-hardness describes worst-case computational complexity, which means that the hardest problems decide NP-hardness for a particular problem type.

0

The TSP has to be modified to a decision problem for it to be quickly checkable. Plus there is an issue of discretization for the Euclidean TSP. A comment on the human performance: http://en.wikipedia.org/wiki/Travelling_salesman_problem#Human_performance_on_TSP

2

One quickly checks "whether a solution for the TSP (travelling salesman problem) is true" by quickly solving a coNP-complete problem. I don't know how much asking about uniqueness changes the situation.

0

Recall that NP is closed under intersection. Hence $L_1\cap\overline{L_2}$ is in NP. Finally we can realize that the symmetric difference of this set and $L_1$ is exactly $L_1\cap L_2$.

0

A proof by induction on the length $n$ of $w$: Base case: The only possibility is a derivation of the form $S_0 \rightarrow a$ for some $a \in \Sigma$ where $S_0$ is the start variable. This is true because any other rule from $S_0$ would be of the form $S_0 \rightarrow AB$ where $A$ and $B$ are variables, neither of which can terminate in $\varepsilon$. So ...

Top 50 recent answers are included