Tag: prove

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?

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<u.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 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 classification problem with the instance domain being $ X = R$ .

For every $ n ∈ N$ let $ H_n$ be the class of polynomial classifiers of degree $ n$ ; namely, $ H_n$ is the set of all classifiers 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$ .