<p>The existence of one way functions is an open problem. As is whether the subset sum problem is solvable with a polynomial time algorithm.</p>

CC BY-SA 4.0
2024-07-05T07:37:34.443Z
2024-07-05T07:37:34.443Z
Mikko Pitkonen
<p>I have difficulties checking whether <span class="math-container">$f^{-1}(x)$</span> is a one way function. <span class="math-container">$x \leq 2^n$</span> is the sum that we want the set of numbers <span class="math-container">$a_1,...,a_m$</span> to be. <span class="math-container">$m \leq 2^n$</span>.
There are <span class="math-container">$4^n$</span> different ways to sum up to a number <span class="math-container">$x$</span> but I did not get any further in checking if this is a one way function.
Can someone help me?</p>

CC BY-SA 4.0
2024-07-05T11:51:44.773Z
The question is unclear. What is $f$? Please don't start sentences with mathematical formulas, it's awful. And state your question in the text. Asking "Can someone help me?" is not a good question.
Andrej Bauer
<np-hardness><one-way-function>
is the set of all numbers that sum up a subset sum problem a one way function?
Prudence Clearwater
# is the set of all numbers that sum up a subset sum problem a one way function?

(Asked by: username_0 on 2024-07-05)

I have difficulties checking whether $f^{-1}(x)$ is a one way function. $x \leq 2^n$ is the sum that we want the set of numbers $a\_1,...,a\_m$ to be. $m \leq 2^n$.
There are $4^n$ different ways to sum up to a number $x$ but I did not get any further in checking if this is a one way function.
Can someone help me?

**Tags:** np-hardness, one-way-function
> **Comments:**
> **username_1**: The question is unclear. What is $f$? Please don't start sentences with mathematical formulas, it's awful. And state your question in the text. Asking "Can someone help me?" is not a good question.  

---

## 1 answers

### Answer by username_2 on 2024-07-05. Score: 0

The existence of one way functions is an open problem. As is whether the subset sum problem is solvable with a polynomial time algorithm.


---

