Score:0

การพิสูจน์ผลลัพธ์ของฟังก์ชันทั่วไป

ธง ma

มีโครงสร้างทั่วไปเพื่อพิสูจน์ความถูกต้องของผลลัพธ์ของฟังก์ชันหรือไม่? กล่าวอีกนัยหนึ่ง มีวิธีทั่วไปในการเป็นพยานสำหรับคำแถลงหรือไม่ $y = ฉ(x)$?

ให้อย่างเป็นทางการมากขึ้น $f: X \ลูกศรขวา Y$ เป็นฟังก์ชันทั่วไป ที่ให้ไว้ $f$มีวิธีทั่วไปในการสร้างฟังก์ชั่นการสร้างพยานหรือไม่ $p: X \ลูกศรขวา W$ และข้อเสนอ $V(x, y, w)$ เช่นนั้นสำหรับทุกคน $x$, เท่านั้น $V(x, f(x), p(x))$ เป็นความจริงและตรวจสอบได้ $V(x, y, w)$ เร็วกว่าการคำนวณ $ฉ(x)$?

Maarten Bodewes avatar
in flag
ฟังก์ชันทางเดียวหักล้างสิ่งนี้ไม่ได้ใช่ไหม
poncho avatar
my flag
ฟังก์ชันหนึ่งที่อาจเป็นตัวอย่างแย้งคือฟังก์ชัน $f(x)=0$ (สำหรับ $x$ ใดๆ); ใช่ มันเป็นเรื่องง่ายที่จะสร้างข้อเสนอสำหรับ $f$ นี้; ฉันไม่รู้ว่าคุณสามารถสร้างอันที่ทำงาน **เร็วกว่า** กว่าการคำนวณ $f$...
ma flag
@poncho นั่นเป็นจุดที่ค่อนข้างยุติธรรมฉันเดา
Wilson avatar
se flag
เพื่อชี้แจงว่าฉันอ่านถูกต้องหรือไม่ คุณกำลังสงสัยว่ามีอัลกอริธึมการตรวจสอบที่รวบรัดและมีประสิทธิภาพหรือไม่ (ในเวลาน้อยกว่าการประเมินฟังก์ชัน) เพื่อตรวจสอบว่าสำหรับ f, x และ y สาธารณะนั้น y=f(x) หรือไม่
ma flag
@วิลสัน แม่น! ฉันรู้ว่ามันมีอยู่สำหรับบางฟังก์ชัน (เช่น ฟังก์ชันทางเดียวสามารถใช้เอาต์พุตเป็นพยานได้) ดังนั้นฉันจึงสงสัยว่ามีกลไกทั่วไปมากกว่านี้หรือไม่!
Wilson avatar
se flag
พิจารณาฟังก์ชันทั่วไป f ที่แสดงโดยชุดของวงจรเลขคณิต ปัญหานี้แก้ไขไม่ได้ด้วยการประมวลผล SNARK ล่วงหน้าใช่หรือไม่ ความซับซ้อนของเวลาตัวตรวจสอบคือโพลีลอการิทึมในความซับซ้อนของวงจร นอกจากนี้ยังมีวรรณกรรมที่เรียกว่าการคำนวณที่ตรวจสอบได้ซึ่งอาจเป็นสิ่งที่คุณกำลังมองหา
Wilson avatar
se flag
ลองใช้ตัวอย่างย้อนกลับของเสื้อปอนโชในบริบท $f(x)=0$ เป็นฟังก์ชันที่คำนวณได้ในเวลาคงที่ ดังนั้น ปัจจัยคงที่ในอัลกอริทึมการตรวจสอบจะมีค่ามากกว่าความซับซ้อนของลอการิทึม แต่สำหรับฟังก์ชันที่ไม่สำคัญ วิธีนี้จะเอาชนะการประเมินค่าฟังก์ชัน

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา