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?

Thanks for your help!

$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.

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!