About this document

NP-Completeness of Cryptarithm Puzzles by Kushal raj is a document available to read on EtoBox.

This document summarizes a proof that solving cryptarithm puzzles, where letters are assigned digits to make arithmetic equations true, is an NP-complete problem. The author first shows that cryptarithms are in NP by describing how solutions can be verified quickly. Then, the author reduces the Boolean satisfiability problem to cryptarithms by constructing a puzzle from a Boolean formula such that the puzzle has a solution if and only if the formula is satisfiable. Finally, the author describes how to assig

Author

Kushal raj

Language

EN