Tag Info

New answers tagged

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 ...


2

In light of the detailed solution of @Marko Riedel, if you only want to show that $T(n)=O(n)$, you can make the (somewhat easier computation): Base case: (ok) Inductive Hypothesis: $T(k)\leq Ck$ for $k<n$ for some constant $c>0$. Then, prove the inductive step: \begin{align*} T(n) &= T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4))+4n \\ &\leq ...


3

Suppose we start by solving the following recurrence: $$T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + 4n$$ where $T(1) = c$ and $T(0) = 0.$ Now let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ be the binary representation of $n.$ We unroll the recursion to obtain an exact formula for $n\ge 2$ $$T(n) = c [z^{\lfloor \log_2 n \rfloor}] ...


1

Let's focus on the topic of whether the matrix determinant's $O(n^3)$ floating point complexity of standard approaches (elimination or factorization) can be improved by having "an upper bound". Knowing an upper bound on the determinant of a matrix does not immediately help lower the complexity of its computation. In the case of real (or complex) matrices, ...


2

How about any functions $f$ and $g$ satisfying $f(1) = 1$, $f(2)=0$, $g(1) = 0$, and $g(2)=1$ ?


5

Consider $$ f(n)=\left\{\begin{array}{lll} n & \text{if} & n \,\,\text{odd}, \\ 1 & \text{if} & n \,\,\text{even}, \end{array}\right. $$ and $$ g(n)=\left\{\begin{array}{lll} 1 & \text{if} & n \,\,\text{odd}, \\ n & \text{if} & n \,\,\text{even}. \end{array}\right. $$


1

$$ f(n) = n^2 \sin^2{an}, \qquad g(n) = n^2 \cos^2{an} $$ Then $$ \frac{f(n)}{g(n)} = \tan^2{an}, \qquad \frac{g(n)}{f(n)} = \cot^2{an}. $$ Choose $a = \pi/2$ for the most obvious problems.


4

Just choose $$ f(n)=\frac{1}{|\sin n|}, \quad g(n)=\frac{1}{|\cos n|}.$$ You have that $$ \frac{f(n)}{g(n)}= |\textrm{cotg } n|,\quad \frac{g(n)}{f(n)}=|\tan n|, $$ and none of those are bounded.


0

Using Hadamard's inequality: $$\det(M)\leq\prod_{i=1}^{N} m_{ii}.$$ one can at least state, the the determinants sign is negative if the product sum of the diagonal elements is at most zero. Nevertheless, I'm struggling by myself finding the lower bound. Yours tcsh


1

Is there a way of computing the $n$th number of a Lucas Sequence of the first kind (given parameters $P$ and $Q$) directly, without calculating each prior value in the sequence? Yes (assuming $P^2 \ne 4Q$), but it's unlikely to give any computational advantage: $$U_n(P,Q) = \frac{a^n - b^n}{a - b}$$ where $$a = \frac{P+\sqrt{P^2 - 4Q}}{2}\\ b = ...



Top 50 recent answers are included