3 ms·

Framing this as inverting a function is interesting, but raises a question, since any function that maps multiple inputs to the same output is not invertible.

Framing this as inverting a function is interesting, but raises a question, since any function that maps multiple inputs to the same output is not invertible. For example, let's say we invert a checker algorithm and "run it backward from YES". Does that find an arbitrary single solution? Does it find all solutions? What if there are an infinite number of solutions?

LegionMammal978 2y ago
"An arbitrary single solution" would be the proper answer for NP. The goal is to find some solution that the verifier accepts, like how in SAT the goal is to find some satisfying assignment for all clauses.
delusional 2y ago
Given that there is potentially an exponential number of solutions, it would be impossible to enumerate them all in anything smaller than exponential time.
- chupasaurus 2y ago
  There is potentially a factorial number of solutions for NP-complete problems.
cvoss 2y ago
In some contexts, the inverse of a function f : A -> B is defined as a function g : B -> A such that g(f(x)) = x and f(g(y)) = y for all x,y. In other contexts, what is meant is g : B -> 2^A such that x is in g(f(x)) for all x and f(x') = f(x) for all x' in g(f(x)). Here, g is said to produce the pre-image under f, and is a generalization of the above definition of inverse for non-injective functions. In other contexts still, what is meant is g : B -> A such that f(g(y)) = y for all y such that there exists some x with f(x) = y. This is a different generalization called a one-sided inverse. (People probably call it a left inverse or right inverse, but I can never remember which is which because it emerges from an arbitrary notational convention.) The article uses inverse in this third sense. "Find some input to f which would yield a given output y, if one exists."
analog31 2y ago
Informally, an example of this problem is calculus class. A kid who's interested in programming, and takes calculus, can dream up a program that computes the derivative of any expression. But now try doing that with the anti-derivative. And to be sure you can write an expression in multiple ways, but the core problem remains. Disclosure: I was that kid. My program was a mess, but good enough for a proof of concept.
afiodorov 2y ago
Idea is to add enough constraints to the function so that inverting it is non trivial (where inverts finds ANY input). Like the video said inverting multiplication with the output of 15 could yield 15 = 15 * 1, so just make the function f(a, b) = a * b where a > 1 and b > 1 for a more interesting RSA-breaking case.
vasekrozhon 2y ago
Hi, a few commenters on Youtube also asked us this question. I just now added the last section to the blog post that discusses it. Basically, although we only show how to find one arbitrary solution, you can use this trick to also find all of them efficiently in terms of the size of the input and the number of solutions.

LegionMammal978 2y ago

"An arbitrary single solution" would be the proper answer for NP. The goal is to find some solution that the verifier accepts, like how in SAT the goal is to find some satisfying assignment for all clauses.

delusional 2y ago

Given that there is potentially an exponential number of solutions, it would be impossible to enumerate them all in anything smaller than exponential time.

chupasaurus 2y ago
There is potentially a factorial number of solutions for NP-complete problems.

cvoss 2y ago

In some contexts, the inverse of a function f : A -> B is defined as a function g : B -> A such that g(f(x)) = x and f(g(y)) = y for all x,y. In other contexts, what is meant is g : B -> 2^A such that x is in g(f(x)) for all x and f(x') = f(x) for all x' in g(f(x)). Here, g is said to produce the pre-image under f, and is a generalization of the above definition of inverse for non-injective functions. In other contexts still, what is meant is g : B -> A such that f(g(y)) = y for all y such that there exists some x with f(x) = y. This is a different generalization called a one-sided inverse. (People probably call it a left inverse or right inverse, but I can never remember which is which because it emerges from an arbitrary notational convention.) The article uses inverse in this third sense. "Find some input to f which would yield a given output y, if one exists."

analog31 2y ago

Informally, an example of this problem is calculus class. A kid who's interested in programming, and takes calculus, can dream up a program that computes the derivative of any expression. But now try doing that with the anti-derivative. And to be sure you can write an expression in multiple ways, but the core problem remains. Disclosure: I was that kid. My program was a mess, but good enough for a proof of concept.

afiodorov 2y ago

Idea is to add enough constraints to the function so that inverting it is non trivial (where inverts finds ANY input). Like the video said inverting multiplication with the output of 15 could yield 15 = 15 * 1, so just make the function f(a, b) = a * b where a > 1 and b > 1 for a more interesting RSA-breaking case.

vasekrozhon 2y ago

Hi, a few commenters on Youtube also asked us this question. I just now added the last section to the blog post that discusses it. Basically, although we only show how to find one arbitrary solution, you can use this trick to also find all of them efficiently in terms of the size of the input and the number of solutions.