Join Log in
Score:1
SugarDrink avatar Crypto

Pseudo Random Generators

in flag
SugarDrink

G is a PRG and takes in a seed s. Is G'(s) = [G(s)]' (i.e. the complement of G(s)) a PRG as well?

My proof by contradiction: Suppose G' is not a PRG, then G''(s) = [[G(s)]']' = G(s) is also not a PRG which is a contradiction, since our initial assumption is that G is a PRG.

Does this proof make sense? Can anyone point out any mistake(s) made?

223
0 + 0
Score:3
fgrieu avatar Crypto
ng flag
fgrieu

This proof is wrong.

It's tried to prove the proposition "the complement of any function that is a PRG is a PRG" by contradiction. The contrary of that proposition is not "the complement of any function that is a PRG is a not a PRG", which is used in the attempted proof to justify the equation after "then".

The correct contrary is "there exists a function that is a PRG which complement is not a PRG", and a proof by contradiction must start from that (as the proposed proof does), and conclude a contradiction, without making unwarranted hypothesis. Hint: a correct proof will use the definition of "is a PRG".

Meta-argument that the question's proof is wrong (but not telling where): the argument used works just as well if we change "a PRG" into "identity" in the statement of the proposition to prove, and reaches the false conclusion that "the complement of any function that is identity is identity".

General hint: it's typically useful to write and use definition(s) involved in the statement of a proposition to prove or disprove.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.