There are several pseudorandom number generators that we have no known polynomial time algorithms for inverting (finding the initial seed). Is it correct to say that inverting these generators is an NP problem?
1
-
1$\begingroup$ Have you read the definition of NP? Have you tried applying it? Where did you get stuck? Have you tried formulating a precise decision problem / search problem that formalizes the notion of "inverting a pseudorandom generator"? Do you know the difference between NP and NP-complete? $\endgroup$– D.W. ♦Mar 16, 2018 at 22:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
NP contains decision problems. Problems with a yes or no answer. Finding $x$ such that $g(x) = y$ for some given pseudo-random generator $g$ and output $y$ isn't a decision problem. It's a function problem.
You can turn this into decision problem by asking whether the $i$'th bit of $x$ is 1 instead. Then you can still find $x$ by just asking this question once for every bit.
Now this problem of deciding on the $i$'th bit is trivially in NP. Speaking informally, every problem that has efficiently verifiable proofs is in NP. $x$ is just such a proof. You can quickly check it's $i$'th bit. And you can quickly check that $g(x) = y$.
answered Mar 17, 2018 at 0:16