PRG 是關於輸入串聯的 PRG
這是一個家庭作業，所以我不期待完整的解決方案，只是一般的指導。
讓一個 PRG $ G:\left{ 0,1\right} ^{n}\to\left{ 0,1\right} ^{l\left(n\right)} $ （在哪裡 $ l\left(n\right) $ 是多項式並且 $ l\left(n\right)>n $ ).
是 $ G’:x\mapsto G\left(x|x\right) $ 一個PRG？（在哪裡 $ | $ 是連接運算符）。
我的直覺（這可能是錯誤的）說不是，因為 $ \left|Im\left(G’\right)\right|\leq2^{n} $ 然而 $ \left|Im\left(U_{l\left(2n\right)}\right)\right|=2^{l\left(2n\right)}>2^{2n} $ .
但是我不確定如何展示這一點。
我想顯示一個區別 $ U_{l\left(2n\right)} $ 和 $ G’\left(U_{n}\right) $ 具有不可忽視的優勢，所以我得到了輸入 $ z\in\left{ 0,1\right} ^{2n} $ 並且需要決定它來自哪個發行版。
我想只是檢查是否 $ z\in Im\left(G’\right) $ ，但這可能需要 $ 2^{n} $ 計算。
我會喜歡一些方向。謝謝！
我想我找到了解決方案。
假設這樣的 G 存在（PRG）。
那麼這裡描述的 G’也是一個 PRG。
但是應用到 $ x|x $ 結果是 $ G’’:x\mapsto G\left(x\right)\circ G\left(x\right) $ ，這不是 PRG（易於構造一個區分器來檢查其輸入是否 $ z=z’|z’ $ ).
也可以使用 $ G′:\left(x|y\right)↦x|G\left(y\right) $ 反而。