Suppose I have two sets $ A$ and $ B$ containing integers. Let $ B’$ be the power set of $ B$ . Then suppose I have an algorithm that enumerates all possible pairings of elements in $ A$ and $ B’$ to apply a function $ f$ to them and check something. How can I prove this algorithm is NP-Hard?

# Tag: Proving

## Problem with proving that $RP \subseteq NP$ : a non-deterministic TM for a language $L \in RP$

I’m having a small issue with wikipedia’s proof that $ RP \subseteq NP$ :

An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic Turing machines where the machine accepts if and only if at least some constant fraction of the computation paths, independent of the input size, accept. NP on the other hand, needs only one accepting path, which could constitute an exponentially small fraction of the paths. This characterization makes the fact that RP is a subset of NP obvious.

My problem lies in the following statement: "…accepts if and only if at least some constant fraction of the computation paths, independent of the input size, accept"

My question is: for a language $ L \in NP$ , wouldn’t it only need one computation path for the non-deterministic TM to accept? Since, if $ x \in L$ , $ P[T(x) accepts] >= 1/2$ with $ T$ being the Turing machine that decides $ L$ .

## Euclidean geometry theorem proving complexity

Euclidean geometry is complete, so the problem of determining whether a statement $ A$ is provable is computable. Do we know its time complexity?

## Why is the proof complete after proving only for one induction when we have more than one variable?

So I’m self-learning coq. And I came across the proof for associativity in addition `forall (a b c : nat)`

Appearntly when we do `induction a.`

after `intros a b c.`

, it creates 2 subgoals

and afterwards we simply need to show that the two sides in both subgoals are equivalent, and the proof is completed.

So I’m just wondering why we don’t need to do `induction b.`

and `induction c.`

to complete the proof? Why only performing induction on `a`

is able to complete the proof?

Or in other words, how come in the function that returns the proof, we just get `b`

and `c`

for “free”? Constructively don’t we need something like a double induction applied twice?

## When proving a set is not regular is it enough to prove a subset of it regular?

E.g. when proving L = {w in {a,b}^*: the first, the middle, and the last characters of w are identical}, can i just prove ab^pab^pa is not regular? Where p is the pumping length?

## Proving injectivity for an algorithm computing a function between sets of different types of partitions [closed]

I am attempting to solve the following problem:

Let $ A$ be the set of partitions of $ n$ with elements $ (a_1, \dots, a_s)$ such that $ a_i > a_{i+1}+a_{i+2}$ for all $ i < s,$ taking $ a_{s+1} = 0.$ Define $ g_n = F_{n+2}-1$ and let $ B$ be the set of partitions of $ n$ as $ b_1 \ge \dots \ge b_s$ such that $ b_i \in \{g_n\}$ for all $ i,$ and if $ b_1 = g_k$ for some $ k,$ then $ g_1, \dots, g_k$ all appear as some $ b_i.$ Prove $ |A|=|B|.$

**Attempt:** Let $ e_i$ be the vector with $ 1$ at position $ i$ and $ 0$ elsewhere. If $ b_1 = g_k,$ let $ c=(c_k, \dots, c_1)$ count how many times $ g_i$ appears. We calculate $ f: B \to A$ as follows:

Let $ c=(c_k,\dots,c_1), a=(0,\dots,0).$ While $ c \ne 0,$ let $ d_1 > \dots > d_k$ be the indices such that $ c_{d_i} \ne 0.$ Replace $ c, a$ with $ c-(e_{d_1}+\dots+e_{d_k}), a+(g_{d_1} e_1 + \dots + g_{d_k} e_k)$ respectively. After the while loop ends, let $ f(b)=a.$

Let $ \sum a, \sum b, \sum c$ be the sum of the components of $ a, b, c$ respectively. Since $ \sum c$ decreases after every loop, the algorithm terminates and $ f(b)$ is well-defined. Since $ c_k g_k + \dots + c_1 g_1 + \sum a$ does not change after every iteration, is $ \sum b$ at the start and $ \sum a$ at the end, we have $ \sum f(b) = \sum b = n,$ so $ f(b)$ is also a partition of $ n.$ Now $ a = (g_k, \dots, g_1)$ after the first loop, which satisfies the condition $ g_i > g_{i-1}+g_{i-2}$ since $ g_i = F_{n+2}-1 = (F_{n+1}-1)+(F_n-1)+1 > g_{i-1}+g_{i-2}.$ Furthermore, after every iteration of the loop, the difference $ a_i – (a_{i-1}+a_{i-2})$ changes by $ 0, g_{d_j}-g_{d_{j-1}} > 0,$ or $ g_{d_j}-(g_{d_{j-1}}+g_{d_{j-2}}) > 0,$ so we have $ a_i > a_{i-1} + a_{i-2}$ at the end and hence $ f(b) \in A.$ Thus, $ f: B \to A$ is well-defined.

In order to prove the injectivity of $ f,$ it suffices to prove each loop iteration as a mapping $ (c,a) \to (c’,a’)$ is injective, which would imply the mapping $ (c,0) \to (0,a)$ that the while loop creates is injective. Indeed, if $ f(b_1) = f(b_2) = a$ with $ (c_1, 0), (c_2, 0)$ being sent to $ (0, f(b_1)) = (0,a), (0, f(b_2)) = (0,a)$ respectively, then we have $ (c_1, 0) = (c_2, 0) \Rightarrow c_1 = c_2 \Rightarrow b_1 = b_2.$

Suppose $ d_1 > \dots > d_i, f_1 > \dots > f_j$ are the non-zero indices of $ c_1, c_2$ respectively and $ c_1 – (e_{d_1}+\dots+e_{d_i}) = c_2 – (e_{f_1}+\dots+e_{f_j}), a_1+g_{d_1}e_1 + \dots+ g_{d_i} e_i = a_2 + g_{f_1} e_1 + \dots + g_{f_j} e_j.$ If $ x \ge 2$ is an entry of $ c_1,$ it decreases by $ 1,$ so the corresponding entry in $ c_2$ after $ c_2$ is modified is also $ x-1,$ which means it must’ve been $ (x-1)+1 = x$ before since $ x-1>0.$ Thus, if the values of two positions of $ c_1, c_2$ differ, one is $ 1$ and the other is $ 0.$ However, if $ c_1 = (1,0), a_1 = (3,1), c_2 = (0,1), a_2 = (4,1),$ then $ (a_1, c_1), (a_2, c_2)$ both get sent to $ ((5,1), (0,0)).$ I can rule out this specific example by arguing that one of the pairs is illegal and could not have come from any choice of initial $ c,$ but I have no idea on how to do this in general.

What should I do next in order to show $ f$ is injective? Furthermore, since the problem I’m trying to prove is correct, injectivity would imply $ f$ is secretly a bijection. But I have no clue on how to even start on the surjectivity of $ f,$ so I just constructed a similar algorithm for $ g: A \to B$ in the hopes of proving $ g$ is injective too. If I can show $ f$ is injective I will probably know how to show $ g$ is.

Here is an example of $ f, g$ in practice:

Let $ n = 41, b = (12, 7, 7, 4, 4, 2, 2, 2, 1) \Rightarrow c = (1, 2, 2, 3, 1).$

$ $ ((1, 2, 2, 3, 1), (0,0,0,0,0)) \to ((0, 1, 1, 2, 0), (12, 7, 4, 2, 1)) \to ((0, 0, 0, 1, 0), (19,11,6,2,1)) \to ((21,11,6,2,1),(0,0,0,0,0)),$ $ so $ f(b) = (21,11,6,2,1).$

Let $ a = (21, 11, 6, 2, 1).$

$ $ ((21,11,6,2,1),(0,0,0,0,0)) \to ((9,4,2,0,0), (1,1,1,1,1)) \to ((2,0,0,0,0),(1,2,2,2,1)) \to ((0,0,0,0,0),(1,2,2,3,1)),$ $ so $ g(a) = (12, 7, 7, 4, 4, 2, 2, 2, 1).$

## help with proving combinatorial identity [migrated]

seems hard to prove the next identity. i think the direction is through **combinatorics** reasons. thanks.

## Proving a certain primitive recursive function exists

Assume $ f\colon ω × ω → ω$ is a computable function. How can we prove that there is a primitive recursive function $ g\colon ω × ω → ω$ where the following holds:

$ ∀n [∃s(f(n, s) = 1) ↔ ∃k(g(n, k) = 1)]$

So for every $ n$ , there is an $ s$ such that $ f(n, s) = 1$ if and only if there is a $ k$ such that $ g(n, k) = 1$ .

Been working on this problem for a while now, if anyone could please help?

## proving $E_{TM}$ is undecidable using the halting language

How to prove that:

$ E_{TM} = \{\langle M\rangle\mid M \ is\ a\ TM\ and\ L(M)=\emptyset\}\notin R$ (is undecidable)

using the language:

$ H_{halt}=\{(⟨M⟩,w):M\ halts\ on\ w\}$ .

I tried to prove by contradiction that assuming $ E_{TM}\in R$ I have a Turing machine which decides $ E_{TM}$ and to construct with it a turing machine which decides $ H_{halt}$ but I don’t know how to do so.

## Proving the recurrence for the “number of ways to make change” problem

I’m studying the famous making change problem. (Post 1 and Post2).

Suppose you were given three coins (1, 2, and 5) and a bill of amount 10 and you want to compute the number of ways you could exchange the bill into coins. In this specific example, there are 4 ways.

The solution involves ordering the coins from the largest to the smallest (5, 2, 1). We then can divide the solution into three subproblems:

(1) the number of ways to change using coins (1) and amount (10 – 1). Call it $ F_1(10-1)$ .

(2) the number of ways to change using coins (1,2) and amount (10 – 2). Call it $ F_2(10-2)$ .

(3) the number of ways to change using coins (1,2,5) and amount (10 – 5). Call it $ F_3(10-5)$ .

The final recurrence would be $ F(10) = F_1(10-1) + F_2(10-2) + F_3(10-5)$ .

I understand the intuition and usually dynamic programming problems have very straight forward proofs (Cut and Paste Arugments). But with this problem, I have no idea where to start? The proof is usually by contradiction and arguing how it’s not possible for $ F(n)$ not to be the optimal value. But I’m not sure here. Any hints on how to even start with this proof? Basically, why is the above recurrence correct?