ในวิทยาการคอมพิวเตอร์เชิง ทฤษฎี อัลกอริทึมการรับรองคืออัลกอริทึมที่ส่งออกพร้อมกับวิธีแก้ปัญหาที่แก้ไข พร้อมทั้งหลักฐานว่าวิธีแก้ปัญหานั้นถูกต้อง อัลกอริทึมการรับรองจะถือว่ามีประสิทธิภาพหากเวลาการทำงานรวมของอัลกอริทึมและตัวตรวจสอบหลักฐานช้ากว่าอัลกอริทึมที่ไม่รับรองที่ดีที่สุดที่รู้จักสำหรับปัญหาเดียวกันไม่เกินปัจจัยคงที่^{[ 1 ]}

หลักฐานที่สร้างขึ้นโดยอัลกอริทึมการรับรองควรจะเรียบง่ายกว่าตัวอัลกอริทึมเองในบางแง่ มิฉะนั้นอัลกอริทึมใดๆ ก็อาจถูกพิจารณาว่าเป็นการรับรองได้ (โดยที่ผลลัพธ์ได้รับการตรวจสอบโดยการเรียกใช้อัลกอริทึมเดิมอีกครั้ง) บางครั้งสิ่งนี้ได้รับการกำหนดเป็นทางการโดยการกำหนดให้การตรวจสอบหลักฐานใช้เวลาน้อยกว่าอัลกอริทึมดั้งเดิม ในขณะที่สำหรับปัญหาอื่นๆ (โดยเฉพาะปัญหาที่สามารถหาคำตอบได้ในเวลาเชิงเส้น ) ความเรียบง่ายของหลักฐานผลลัพธ์จะถูกพิจารณาในแง่ที่ไม่เป็นทางการน้อยกว่า^{[ 1 ]}ตัวอย่างเช่น ความถูกต้องของหลักฐานผลลัพธ์อาจชัดเจนต่อผู้ใช้ที่เป็นมนุษย์มากกว่าความถูกต้องของอัลกอริทึม หรือตัวตรวจสอบหลักฐานอาจเหมาะสมกับการตรวจสอบอย่างเป็นทางการมากกว่า^{[ 1 ] [ 2 ]}

การนำอัลกอริทึมการรับรองที่รวมถึงตัวตรวจสอบสำหรับหลักฐานที่สร้างโดยอัลกอริทึมมาใช้งาน อาจถือได้ว่ามีความน่าเชื่อถือมากกว่าอัลกอริทึมที่ไม่รับรอง เพราะเมื่อใดก็ตามที่อัลกอริทึมทำงาน จะเกิดสิ่งใดสิ่งหนึ่งในสามสิ่งต่อไปนี้: มันจะสร้างผลลัพธ์ที่ถูกต้อง (กรณีที่ต้องการ) มันจะตรวจพบข้อบกพร่องในอัลกอริทึมหรือผลที่ตามมา (ไม่ต้องการ แต่โดยทั่วไปแล้วดีกว่าการดำเนินการต่อไปโดยไม่ตรวจพบข้อบกพร่อง) หรือทั้งอัลกอริทึมและตัวตรวจสอบมีข้อบกพร่องในลักษณะที่ปกปิดข้อบกพร่องและป้องกันไม่ให้ตรวจพบ (ไม่ต้องการ แต่ไม่น่าเป็นไปได้ เนื่องจากขึ้นอยู่กับการมีอยู่ของข้อบกพร่องอิสระสองข้อ) ^{[ 1 ]}

ตัวอย่างของปัญหาเกี่ยวกับอัลกอริธึมที่ตรวจสอบได้จำนวนมากมาจากทฤษฎีกราฟตัวอย่างเช่น อัลกอริธึมแบบคลาสสิกสำหรับการทดสอบว่ากราฟเป็นกราฟสองส่วนหรือไม่ จะส่งค่าบูลีนออกมา: จริงถ้ากราฟเป็นกราฟสองส่วน เท็จถ้าไม่ใช่ ในทางตรงกันข้าม อัลกอริธึมการรับรองอาจแสดงผลการระบายสี 2 สีของกราฟในกรณีที่เป็นกราฟสองส่วน หรือวงจรที่มีความยาวคี่ถ้าไม่ใช่ กราฟใดๆ จะเป็นกราฟสองส่วนก็ต่อเมื่อสามารถระบายสีได้ 2 สี และไม่ใช่กราฟสองส่วนก็ต่อเมื่อมีวงจรคี่ การตรวจสอบว่าการระบายสี 2 สีถูกต้องหรือไม่ และการตรวจสอบว่าลำดับของจุดยอดที่มีความยาวคี่ที่กำหนดเป็นวงจรหรือไม่ สามารถทำได้ง่ายกว่าการทดสอบความเป็นกราฟสองส่วน^{[ 1 ]}

ในทำนองเดียวกัน เป็นไปได้ที่จะทดสอบว่ากราฟทิศทางที่ กำหนด เป็นกราฟไร้วงจรหรือไม่ โดยใช้อัลกอริทึมการรับรองที่ให้ผลลัพธ์เป็นลำดับเชิงโทโพโลยีหรือวงจรทิศทาง นอกจากนี้ยังเป็นไปได้ที่จะทดสอบว่ากราฟไร้ทิศทางเป็นกราฟคอร์ดั ล หรือไม่ โดยใช้อัลกอริทึมการรับรองที่ให้ผลลัพธ์เป็นลำดับการกำจัด (ลำดับของจุดยอดทั้งหมด โดยที่สำหรับทุกจุดยอด เพื่อนบ้านที่อยู่ภายหลังในลำดับจะก่อตัวเป็นคลิก ) หรือวงจรไร้คอร์ด และยังสามารถทดสอบได้ว่ากราฟเป็นกราฟระนาบหรือไม่ โดยใช้อัลกอริทึมการรับรองที่ให้ผลลัพธ์เป็นฝังระนาบหรือกราฟย่อย Kuratowski ^{[ 1 ]}

อัลกอริทึมยุคลิดแบบขยายสำหรับการหาตัวหารร่วมมากที่สุดของจำนวนเต็มสองจำนวนxและyคือการรับรอง: โดยจะส่งออกจำนวนเต็มสามจำนวนg (ตัวหาร), aและbโดยที่ax + by = gสมการนี้จะเป็นจริงได้เฉพาะกับพหุคูณของตัวหารร่วมมากที่สุดเท่านั้น ดังนั้นการทดสอบว่าgเป็นตัวหารร่วมมากที่สุดอาจทำได้โดยการตรวจสอบว่าgหารทั้งxและy ลงตัว และสมการนี้ถูกต้อง^{[ 1 ]}

• การตรวจสอบความถูกต้อง (Sanity check)คือการทดสอบง่ายๆ เพื่อตรวจสอบความถูกต้องของผลลัพธ์หรือผลลัพธ์ระหว่างขั้นตอน ซึ่งไม่จำเป็นต้องเป็นการพิสูจน์ความถูกต้องอย่างสมบูรณ์