จะพิสูจน์ความแตกต่างได้อย่างไร?

ฉันสงสัยว่าการคำนวณที่แยกไม่ออกได้รับการพิสูจน์อย่างไร

ตัวอย่างเช่น ต่อไปนี้จะแยกไม่ออกจากการคำนวณหรือไม่ ถ้าเป็นเช่นนั้นเราจะพิสูจน์ได้อย่างไร?

อนุญาต $P_a$ เป็นเครื่องน่าจะเป็นที่รู้ความลับ $a$ และสร้างลำดับของ $n$ สิ่งอันดับ: $(x_1,{x_1}^a),...,(x_n,{x_n}^a)$ ที่ไหน $x_i$ สำหรับแต่ละทูเพิลจะถูกสุ่มตัวอย่างจากกลุ่มวัฏจักรไพรม์ออร์เดอร์ ในทำนองเดียวกันให้ PPT $P_b$ ถูกกำหนด ตอนนี้ให้ผู้ท้าชิงสุ่มเลือกสองลำดับที่สร้างขึ้นโดย $P_a$ และ $P_b$ (อาจเป็นได้ทั้งจาก $P_a$หรืออย่างใดอย่างหนึ่งจาก $P_a$ และหนึ่งจาก $P_b$). อัลกอริทึมหนึ่งที่มีประสิทธิภาพสามารถบอกได้หรือไม่ว่าสองลำดับนั้นถูกสร้างขึ้นโดย PPT สองอันที่ต่างกัน

เราจะถือว่าใช้สมมติฐานมาตรฐานในกลุ่ม เช่น ความยากของลอการิทึมที่ไม่ต่อเนื่องหรือการตัดสินใจของดิฟฟี-เฮลแมน