## Proof that $G$ is a yes-instance of IDS $\iff$ $f(G)$ is a yes-instance of SAT

Consider the Independent Dominating Set problem with a directed graph $$G=(V,E)$$ as instance and the properties that:

1. $$\forall (u,v) \in E, \{u,v\}\nsubseteq S$$
2. $$\forall v \in V: v \in S \lor \exists (u,v) \in E: u \in S$$

then consider the function $$f$$ which is a many-one reduction from IDS to SAT for $$G$$: $$f(G)= \bigwedge_{(u,v) \in E}(\neg x_u \lor \neg x_v) \land \bigwedge_{v \in V}(x_v \lor \bigvee_{(u,v) \in E}x_u)$$

Theorem: $$G$$ is a yes-instance of IDS $$\iff$$ $$f(G)$$ is a yes-instance of SAT

Proof:

$$\Leftarrow$$“: Assume that $$f(G)$$ is a yes-instance of SAT:

Consider the propositional atoms $$x_u$$ and $$x_v$$ which represent the vertices of an edge. $$x$$ is $$true$$ iff is is in $$S$$. To proof a CNF-formula true we have to proof all conjuncted subformulas true.

Now consider since $$\bigwedge_{(u,v) \in E}(\neg x_u \lor \neg x_v)$$ holds and tells us that only one of the vertices $$u,v$$ is allowed to be in $$S$$ at the same time, this implies $$\forall (u,v) \in E, \{u,v\}\nsubseteq S$$.

For the second part we know that $$\bigwedge_{v \in V}(x_v \lor \bigvee_{(u,v) \in E}x_u)$$ only evaluates to true if either $$v \in S$$ or any $$u \in S$$ which is connected by an edge to $$v$$. This implies $$\forall v\in V: v \in S \lor \exists(u,v) \in E: u \in S$$.

Therefore we are done.

Is my proof for “$$\Leftarrow$$” of the theorem correct?

Assumption: The proof is correct and the reduction is valid:

Now we know that IDS is NP-hard, for completeness of IDS we still have to show NP-membership of IDS, right? Furthermore we have to provide an efficient algorithm which uses non-determinism to show that IDS is a member of NP, correct?

## Is the sum $f+g$ of two one-way-functions a one-way-function?

Since there exists a bijection of sets from $$\{0,1\}^*$$ to $$\mathbb{N_0}$$, we might view one-way-functions as functions $$f :\mathbb{N_0} \rightarrow \mathbb{N_0}$$. My question is, suppose $$f,g$$ are one-way-functions, is then $$(f+g)(n):=f(n)+g(n)$$ a one-way-function or can one construct a counterexample? (The length of $$n$$ is $$\text{ floor}(\frac{\log(n)}{\log(2)})=$$ the number of bits to represent $$n$$)

Comment on answer of @Bulat: Suppose $$f$$ is an owf. If (?) there exists a $$k \in \mathbb{N}$$ such that for all $$x \in \mathbb{N_0}$$ we have $$f(x) \le x^k$$. Then as @Bulat mentioned, construct $$g(x) = x^k-f(x) \ge 0$$. Then $$g(x)$$ is an owf as $$f$$ is, but $$h(x) = g(x)+f(x) = x^k$$ is not an owf. So the question is, if there exists such an $$k$$. The argument would also work considering $$k^x$$ instead of $$x^k$$. But the same question remains? Why would such an $$k$$ exist?

Posted on Categories proxies

## $f,g \in [0,1] \times [0,1]$, $\int f – g \mathrm{d}x = 0$ and are monotonically increasing, then $\int |f-g| \mathrm{d}x \le \frac{1}{2}$

$$f,g$$ are monotonically increasing in $$[0,1]$$ and $$0\le f , g \le 1$$. $$\int_0^1 f – g \mathrm{d}x = 0$$. Prove that

$$\int_0^1 |f – g|\mathrm{d}x \le \frac{1}{2}$$

In my previous question, $$g(x) = x$$. And my teacher said $$x$$ can be replaced by $$g(x)$$. In fact, in previous question, we don’t need to use the condition $$\int_0^1 f – g \mathrm{d}x = 0$$. But if we replace $$x$$ with $$g$$, this condition becomes necessary.

Also, if $$g = x$$, we can replace the $$\frac{1}{2}$$ with $$\frac{1}{4}$$,that is

$$\int_0^1|f-g| \mathrm{d}x \le \frac{1}{4}$$ I am wondering how to prove that.

Posted on Categories proxies

## Prove $fg$ is integrable.

i’m a bit stuck on this question, any answer/hint will be greatly appreciated. Thanks.
So here is the question:
Let $$f,g:[a,b] \to \mathbb{R}$$ be functions such that $$f$$ is integrable, $$g$$ is continuous, and $$g(x)>0$$ for all $$x \in [a,b]$$. Since both $$f,g$$ are bounded, let $$K>0$$ be such that $$|f(x)|\leq K$$ and $$g(x) \leq K$$ for all $$x \in [a,b]$$.
(a) Let $$\eta > 0$$ be given. Prove that there is a partition $$P$$ of $$[a,b]$$ such that $$U(P,f)-L(P,f)<\eta\quad \text{ and }\quad M_i(P,g)-m_i(P,g)< \eta$$ for all $$i$$.
(b) Let $$P$$ be a partition as in (a). Prove that for all $$i$$, $$M_i(P,fg)-m_i(P,fg)\leq K(\eta +M_i(P,g)-m_i(P,g)).$$ (c)Let $$P$$ be a partition as in (a). Prove that $$U(P,fg)-L(P,fg) \leq K(b-a+1)\eta.$$ (d)Prove that $$fg$$ is integrable.
I’ve figured out part (a), and regarding the notation,$$U(P,f):=\sum_{i=1}^{n}M_i(P,f)(t_i-t_{i-1})$$ $$L(P,f):=\sum_{i=1}^{n}m_i(P,f)(t_i-t_{i-1})$$ $$M_i(P,f):=\text{sup }f([t_{i-1},t_i])=\text{sup }\{f(t):t\in[t_{i-1},t_i]\}$$ $$m_i(P,f):=\text{inf }f([t_{i-1},t_i])=\text{inf }\{f(t):t\in[t_{i-1},t_i]\}$$ $$P=\{t_0,t_1,\dots,t_n\}\text{ is a partition, }i=1,\dots,n$$ Thanks!