## algorithms – Proving NP-completeness for a not so cheesy problem

Let’s say we have a matrix M(1..B, 1..B) (i.e., a square matrix) and a mouse in the upper left corner (1,1). We also have an integer A, which tells how many pieces of cheese there are in the matrix. The mouse can move from a given positon (i, j) either in the direction (i+1, j) or (i, j+1). When the mouse visits a given position (i,j), it collects all the given cheese immediately, so if it decides to return to an already visited position, it will already be empty. Additionally, the mouse can ONLY reverse/back ONCE when traversing the matrix, because we can assume that this mouse doesn’t particularly like to change its mind.

So given all these prerequisites, the question is whether or not it is possible for the mouse to collect exactly A pieces of cheese, starting from the position (1,1) and ending up in the position (B,B)?

There should be a proof that this problem is NP-complete by showing it is in NP and by reducing the NP-complete problem Subset Sum.

For showing it is in NP I was thinking about maybe looping through the whole matrix and counting the total number of cheese and then maybe have some sort of boolean condition to check whether or not the amount of cheese the mouse has collected equals to the total amount of cheese located in the matrix and that this will take polynomial time to do. However, I am not sure this is the right way to do and I am even more unsure of how to reduce Subset Sum to this problem. Thus, I am grateful for your help and advice!

Posted on Categories Articles

## dg.differential geometry – Proving some identities about the time derivative of the k-th covariant derivatives of scalar curvature under normalized Ricci flow on surfaces

I’m trying to prove the following identities (under the normalized Ricci flow on surfaces, on which $$partial_t g = (r-R)g$$ holds true, where $$r$$ denotes the average scalar curvature and has the same sign as the Euler characteristic):

$$frac{partial}{partial t}left(nabla^{k} Rright)=Delta nabla^{k} R-rleft(nabla^{k} Rright)+sum_{j=0}^{lfloor k / 2rfloor}left(nabla^{j} Rright) otimes_{g}left(nabla^{k-j} Rright)$$

$$begin{array}{l} frac{partial}{partial t}(|nabla^k R |^2) =Deltaleft|nabla^{k} Rright|^{2}-2left|nabla^{k+1} Rright|^{2}-(k+2) rleft|nabla^{k} Rright|^{2} +left(nabla^{k} Rright) otimes_{g}left(sum_{j=0}^{lfloor k / 2rfloor}left(nabla^{j} Rright) otimes_{g}left(nabla^{k-j} Rright)right) end{array}$$

where by $$A otimes_g B$$ we refer to any tensor field which is a finite linear combination of contractions and metric contractions of the tensor product $$A otimes B$$. Now, I’ve already proven that the following hold:

$$partial_{t} nabla R=Delta nabla R+frac{3}{2} R nabla R-r nabla R$$
$$nabla^{n} Delta R-Delta nabla^{n} R=sum_{j=0}^{lfloor n / 2rfloor}left(nabla^{j} Rright) otimes_{g(t)}left(nabla^{n-j} Rright)$$
$$begin{array}{c} nabla^{n} R^{2}=displaystyle{sum_{j=0}^{lfloor n / 2rfloor}left(nabla^{j} Rright) otimes_{g(t)}left(nabla^{n-j} Rright) }\ left(frac{partial}{partial t} Gammaright) otimes_{g(t)}left(nabla^{j} Rright)=(nabla R) otimes_{g(t)}left(nabla^{j} Rright) end{array}$$
$$frac{partial}{partial t}left(nabla_{k_{1}} nabla_{k_{2}} ldots nabla_{k_{n}} Rright)=nabla_{k_{1}}left{partial_t nabla_{k_{2}} ldots nabla_{k_{n}} Rright}-sum_{l=2}^{n}left(partial_{t} Gamma_{k_{1} k_{l}}^{m}right) nabla_{k_{2}} ldots nabla_{k_{l-1}} nabla_{m} ldots nabla_{k_{n}} R$$

So, to prove the first formula for the evolution of $$nabla^k R$$, I used recursive applications of this last identity just above, but I’d like someone to check my work. I noticed there would be terms of the form:

begin{align*} nabla_{k_1} cdots nabla_{k_{n-1}}(partial_t nabla_{k_n} R) &= nabla_{k_1} cdots nabla_{k_{n-1}}(Delta nabla_{k_n}R + frac{3}{2} R nabla_{k_n} R – r nabla_{k_n R}) \ &= nabla_{k_1} cdots nabla_{k_{n-1}} ( nabla_{k_n} Delta R + Sigma + frac{3}{2} R nabla_{k_n} R – r nabla_{k_n R} )\ &=nabla^k Delta R + Sigma – r(nabla^{k} R) \ &=Delta nabla^k R + Sigma – r(nabla^k R) end{align*}

where by $$Sigma$$ I’m denoting $$displaystyle{sum_{j=0}^{lfloor k / 2rfloor}left(nabla^{j} Rright) otimes_{g}left(nabla^{k-j} Rright)}$$ to avoid taking up too much space. The remaining terms are of the form:

begin{aligned} &left(partial_{t} Gammaright) otimes nabla^{k-1} R=nabla R otimes nabla^{k-1} R=Sigma\ &nabla^r(partial_t Gamma) otimes nabla^{k-r-1} R = nabla^{r+1}R otimes nabla^{k-r-1}R = Sigma end{aligned}

and so we have proved the first identity. But I didn’t manage to prove the second one. We have:

begin{aligned} frac{partial}{partial t}left|nabla^{k} Rright|^{2} &= frac{partial}{partial t}left(g^{i_1 p_1} cdots g^{i_k p_k} nabla_{i_1} cdots nabla_{i_k} R nabla_{p_1} cdots nabla_{p_k} Rright) \ &=(R-r)k |nabla^k R |^2 + 2 langle nabla^k R, partial_t(nabla^k R) rangle end{aligned}

and since

begin{align*} 2 langle nabla^k R, partial_t(nabla^k R) rangle &= 2 langle nabla^k R, Delta nabla^k R + Sigma – r nabla^k R rangle \ &=2 langle nabla^k R, Delta nabla^k R rangle + 2 langle nabla^k R, Sigma rangle – 2r |nabla^k R|^2 end{align*}

We’re then left to prove that:

$$2 langle nabla^k R, Delta nabla^k R rangle = -kR |nabla^k R|^2 + Delta |nabla^k R|^2 – 2 |nabla^{k+1} R|^2$$

but I’ve been stuck on this one for a while. I’d really appreciate some help on this! Thanks in advance.

Posted on Categories Articles

## complex analysis – Proving \$f(z)=frac{1}{z}- frac{1}{z-1}\$ is not holomorphic on \$0

I want to prove that $$f(z)=frac{1}{z}- frac{1}{z-1}$$ is not holomorphic on $$0<|z|< 1/2$$.

My original thought was to use Morera’s theorem, to prove that $$oint_gamma f neq 0$$ for some path $$gamma$$. I tried $$gamma$$ as the circle of radius $$frac{1}{2}$$ and I got

begin{align} oint_gamma f = oint_gamma frac{1}{z} – oint_gamma frac{1}{z-1} =2pi i -2pi i=0 end{align}

where each of the integrals is respectively $$2pi i$$ as a result of cauchies integral theorem. Does anybody have a suggestion as to what path to try? Moreover, what is the intuition between the choice of this path?

Posted on Categories Articles

## real analysis – Making sense of a Fourier transform and proving that a function is derivable and is in \$W^{1,1}_text{loc}(0,infty)\$

I have a function $$Vin W^{1,1}_text{loc}(mathbb{R}^ntimesmathbb{R}^+)$$, such that, $$V(x,cdot)in C^0((0,infty))$$, and: $$V(x,0)=u(x)$$, $$forall xinmathbb{R}^n$$,where $$uinmathcal{S}(mathbb{R}^n)$$ is given, moreover form some $$ain(-1,1)$$:
$$int_{mathbb{R}^ntimesmathbb{R}^+}y^a|nabla V(x,y)|^2,dx,dy
by (1), we have that, for a.e. $$y>0$$, $$partial_{x_j}V(cdot,y),partial_y V(cdot,y)in L^2(mathbb{R}^n),$$ so make sense the Fourier transform $$mathcal{F}(partial_yV(cdot,y))in L^2(mathbb{R}^n)$$, for a.e. $$y>0$$. What sense can I give to $$mathcal{F}(V(cdot,y))$$? There is way to prove that $$V(cdot,y)$$ is a tempered distribution? In this case, how i can prove that:
$$mathcal{F}(partial_yV(cdot,y))=partial_ymathcal{F}(V(cdot,y))tag{2}?$$
Morover, set: $$phi(xi,y)=mathcal{F}(V(cdot,y))(xi)$$, $$xiinmathbb{R}^n,y>0$$, fix $$xiinmathbb{R}^n$$ and set $$h(y)=phi(xi,|xi|^{-1}y)$$, is true that $$h$$ is continuos in $$(0,infty)$$? How i can show that:
$$h'(y)=|xi|^{-1}partial_yphi (xi,|xi|^{-1}y),$$
and deduce that: $$hin W^{1,1}_text{loc}(0,infty)$$?
I don’t even know where to start. Please, help me.

These questions arise from the proof of the lemma 4.1.9 of “Some nonlocal operators and effects due to nonlocality”, by C.Bocur, there is link.

Posted on Categories Articles

## Proving something on the Schwarz space and extending to \$L^p\$ space

I am taking a graduate Harmonic Analysis course without having taken a Functional Analysis course (supposed to take it next semester). I have done fine by reading up on whatever odds and bits I have needed but a common manner of proof is proving something on the Schwarz space (or some other dense subspace) and extending to $$L^P$$ space. I haven’t seen these before so I am hoping I can be directed to some reference material with perhaps some prototypical examples of such proofs. Cheers.

## reference request – Proving that \$C_S^{infty}(M,N)\$ is a Baire space

I have been reading Hirsch’s Differential topology and I am sure a lot of you know this book as a lot of typos. I believe one of them is the proof that $$C_S^{infty}(M,N)$$ is a Baire space. I don’t think his proof works, but I hope this is a true fact since it is used throughout the text. Now when he proves that $$C_S^r(M,N)$$ is a Baire space , for $$0 leq r, we just use a continuous function $$J^r:C^r_S(M,N)rightarrow C^0(M,J^r(M,N))$$ such that the image is a weakly closed subset of $$C^0(M,J^r(M,N))$$ and now since $$J^r(M,N)$$ is complete $$M$$ is a manifold and $$J^r$$ is continuous we get that $$C_S^r(M,N)$$ is a Baire space. Now I think he wants to do the same type of argument for $$J^{infty}:C^{infty}(M,N)rightarrow C^0(M,J^{infty}(M,N))$$ but here we don’t have the fact that the function is continuous. So my question is if anyone knows a proof or a reference for seeing that $$C_S^{infty}(M,N)$$ will in fact be a Baire space? Thanks in advance.

Posted on Categories Articles

## algorithm – Proving time complexity of randomized quick sort?

With X a random variable denoting the total number of comparisons in quick sort , how to prove that E(X) ∈ O(n). For each i, j with 1 ≤ i < j ≤ n we define an indicator random variable
Xi,j for the event that the i’th smallest element is compared to the j’th smallest element.
Thus expectation of X

``````E(X) = sum_{i,j | 1≤i<j≤n} E(Xi,j)
``````

By using algorithm that finds kth largest number When estimating each E(Xi,j ), we must consider three cases: i < k < j, i < j ≤ k, and k ≤ i < j. Accordingly, we define:

``````E<> = sum_{i,j | i<k<j} E(Xi,j)
E< =  sum_{i,j | i<j<k} E(Xi,j)
E> =  sum_{i,j | k<i<j} E(Xi,j)
``````

E(X) = E(X<>) + E(X<) + E(X>)

What is E(Xi,j ) when i < k < j?

X<> d = sum_{i,j | i<k<j ∧ j−i=d} (Xi,j)

where d belongs to 2, 3, 4, 5…….n-1

Posted on Categories Articles

## Proving Regressor levels does not change SSt, SSr and SSres [closed]

enter image description here

State assumption in the proof

Posted on Categories Articles

## propositional logic – Proving the validity of a sequent using Modus Tollens

Problem: Prove $$p rightarrow (q vee r), neg q, neg r vdash neg p$$ using Modus Tollens.

I need to prove the validity of the above sequent by using natural deduction. Initially, I didn’t read the entire problem, and went the long way by doing an implication-elimination, two negation-eliminations, an or-elimination, and finally a negation-introduction. Then I read the problem and realized I had to use MT, and now I’m stuck. I don’t have the greatest grasp on propositional logic and natural deduction. Am I allowed to do the following?

Since I have $$neg q$$ and $$neg r$$ as my premises, can I use an and-introduction and do $$neg q wedge neg r$$, which would allow me to immediately use MT to deduce $$neg p$$? If not, could someone point me in the correct direction? Thanks.

Posted on Categories Articles

## graphs – Designing an algorithm that finds two nodes of a distance and proving claims

I have to give an algorithm that finds two nodes whose distance is at least half of the diameter of a graph (Given an undirected connected graph G), knowing that the diameter of a graph is the largest distance between any two nodes. The nodes are unweighted.
The general idea is to run BFS from any arbitrary node, and find two nodes that fulfill the requirement but the difficulty for me lies in formally proving any claim used.

Is a possible solution to have an algorithm that runs BFS from a node to calculate the diameter, and then in the stored list to find two nodes that are at least half that diameter? Or is there a more optimal solution?
I am a first year CS student, so any guidance or help would be appreciated!

Posted on Categories Articles