## Assuming a set is decidable, prove that another set is decidable

Suppose we’re dealing with programs that output zeros and ones. Consider all such programs (in a fixed language) having at most n instructions. For each program in this finite set, look at how many ones the program produces when we run it on the empty argument. Call this number one(n).

Consider the set $$\{\langle a,b\rangle :one(a)=b\}$$ where $$\langle \rangle$$ is the Cantor pairing function. Assuming that this set is decidable (there is an oracle telling us the answer), how to prove that $$K=\{x:\phi_x(x)\downarrow\}$$ is decidable? (i.e. how to show that $$K$$ is decidable using that set above as an oracle)

## How to formally prove the dependencies of a computer malware?

I’m in the process of the writing a thesis. A small part of it is to prove that certain malware have certain dependencies which must first be satisfied before they are successful in infecting the host. For instance, a virus must first get on the host and then start executing before infection.

• Dependency 1: getting on the host
• Dependency 2: executing

We know these dependencies to be true from experience and common sense, however, how would be go about formally proving these in computer science? I am not asking for all the proofs (I realize that that’s my job!), but just how to approach them since right now I see no way to formally prove it.

## How do I prove that 3-coloring is NP (not NP-complete quite yet)?

I’m trying to prove that the following language (3-coloring) is NP:

$$3COLOR$$ = {< G > | G is an undirected graph with a legal 3-coloring}

I know that I have to construct a non-deterministic Turing Machine $$M$$ for 3COLOR and if $$M$$ runs in polynomial time, the problem is in class $$NP$$. Though, can someone help me construct the actual Turing Machine to better understand its time complexity? I don’t understand why this is $$NP$$.

Thank you.

## Prove the Droid Trader Problem is NP-complete

This question is from Algorithms Design.

A player in the game controls a spaceship and is trying to make money buying and selling droids on different planets. There are $$n$$ different types of droids and $$k$$ different planets. Each planet $$p$$ has the following properties: there are $$s(j, p) \geq 0$$ droids of type $$j$$ available for sale, at a fixed price of $$x(j, p) \geq 0$$ each, for $$j = 1, 2, \dots , n$$, and there is a demand for $$d(j, p) \geq 0$$ droids of type $$j$$, at a fixed price of $$y(j, p) \geq 0$$ each. (We will assume that a planet does not simultaneously have both a positive supply and a positive demand for a single type of droid; so for each $$j$$, at least one of $$s(j, p)$$ or $$d(j, p)$$ is equal to $$0$$.)

The player begins on planet $$s$$ with $$z$$ units of money and must end at planet $$t$$; there is a directed acyclic graph $$G$$ on the set of planets, such that s-t paths in $$G$$ correspond to valid routes by the player. (G is chosen to be acyclic to prevent arbitrarily long games.) For a given s-t path $$P$$ in $$G$$, the player can engage in transactions as follows. Whenever the player arrives at a planet $$p$$ on the path $$P$$, she can buy up to $$s(j, p)$$ droids of type $$j$$ for $$x(j, p)$$ units of money each (provided she has sufficient money on hand) and/or sell up to $$d(j, p)$$ droids of type $$j$$ for $$y(j, p)$$ units of money (so I’m assuming you can make multiple buy/sells at each planet). The player’s final score is the total amount of money she has on hand when she arrives at planet $$t$$.

I’m trying to prove this problem is harder than some NP-complete problem, but I am quite stuck. Since the planets are organized in a DAG, I think the ‘hardness’ of the problem comes from the fact that you can buy and sell many different types of droids at each planet. Also, this problem is a maximation problem, and I don’t know many NP-complete maximization problems other than quadratic assignment.

Can I get a hint on how to do this? Such as what problem X should I choose to reduce to Droid Trader Problem. Thanks!

## How to prove LastToken problem is NP-complete

Consider the following game played on a graph $$G$$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding one token to some neighboring node. The LastToken problem asks whether, given a graph $$G$$ and an initial number of tokens $$t(v) \ge 0$$ for each vertex $$v$$, there is a sequence of moves that results in only one token being left in $$G$$. Prove that LastToken is NP-complete.

I’m learning how to prove NP-complete recently but having trouble to understand the concept of NP. As far as I know, to prove a problem is NP-complete, we first need to prove it’s in NP and choose a NP-complete problem that can be reduced from. I’m stuck on which NP-complete problem that can reduce to my problem. As I interpreted this is sequencing problem and I’m guessing I can either reduce Ham Cycle or Traveling Sales Man to my problem, but I don’t see any connection between them so far. How should I start a good approach?

## Prove that $\text{EF p}$ can’t be written in LTL

Why can’t we somehow represent it’s negation in LTL and go from there? I think maybe because it has (effectively) two existential quantifiers, so negating it does not work. But how do I prove it?

## Given undirected and connected graph G=(V,E). Prove for any DFS run: for any u,v∈V if u.d>v.d then u.d−v.d≥δ(u,v)

Given undirected and connected graph $$G = (V,E)$$. Prove for any DFS run: for any $$u,v \in V$$ if $$u.d>v.d$$ then $$u.d − v.d ≥ δ(u,v)$$

$$δ(u,v)$$-distance of a shortest path (not necessarily unique) in G

$$u.d,v.d$$-time, when each vertex was discovered in DFS for the first time.

I know that DFS not necessarily returns the shortest path.And I know that if $$u.d>v.d$$ then $$u$$ discovered after $$v$$, $$v≠u$$ and there is path is DFS between vertices, because G is connected.

I have tried to assume by contradiction that $$u.d-v.d<δ(u,v)$$

Given that G is connected and $$v.d. Then $$v$$ discovered before $$u$$ and $$u≠v$$. $$u.d-v.d$$ sets distance of some path from $$u$$ to $$v$$ in $$G_π$$. By our assumption this distance is smaller then $$δ(u,v)$$ and that is in contradiction to the fact that $$δ(u,v)$$ is a distance of a shortest path (not necessarily unique) in G.

But this prof is not full. Why can we say the “punch line”?

## How to prove Exact cover problem is NP Complete using Vertex Cover problem?

Using reduction theorem in NP, we want to prove that Exact cover is NPC by reducing it from Vertex Cover Problem. It is easy to derive it from SAT, but we can’t find a solution yet to derive it from Vertex Cover.

## How to prove that this language is not regular?

Given a language $$L$$ over the alphabet {‘[‘, ‘,’, ‘1’, ‘0’} where if $$x \in L$$ then $$x$$ is of the form $$[x_0, \dots, x_n]$$, in which each of the $$x_i$$ represents unique binary strings (so $$x_i = x_j$$ only when $$i=j$$). Prove that this is not a regular language.

Here is what I have. I have used the pumping lemma.

Suppose $$L$$ is a regular language. Let $$M$$ be the DFA that accepts $$L$$. Let $$p$$ be the pumping length of $$L$$. Given $$x = [x_0,\dots,x_p] \in L$$ we see that $$|x| > p$$ so pumping lemma applies, so $$x = UVW$$ where $$|UV| < p$$, $$|v| > 0$$, and $$UV^iW \in L$$.

Now if we have $$UVVW$$ that means $$V$$ is repeating some of the characters in $$x$$ and therefore it must repeat some $$x_i$$. Therefore we have reached a contradiction, which shows that $$L$$ is not a regular language.

Is this a correct proof? If not, what can I do to improve it?

## Prove that the VC dimension of the class of polynomial classifiers of degree $n$ is $n+1$

Consider a binary classiﬁcation problem with the instance domain being $$X = R$$.

For every $$n ∈ N$$ let $$H_n$$ be the class of polynomial classiﬁers of degree $$n$$; namely, $$H_n$$ is the set of all classiﬁers of the form $$h(x) = sign(p(x))$$ where $$p : R \to R$$ is a polynomial of degree $$n$$.

Please prove that $$VCdim(H_n) = n+1$$.