<p>Solving this problem is NP-hard. In particular, even deciding whether there exists an answer key consistent with the given answer choices and scores is NP-complete. We can prove this by reduction from 1-in-3 SAT.</p>

<p>Given a 1-in-3 SAT formula with $c$ clauses and $n$ variables, we construct an instance of your problem with $n$ questions, each with 3 choices, and $c+1$ sample answer/grade pairs.</p>

<p>For each variable $x$, one of the questions is "what is the value of boolean variable $x$?" and the three possible answers are "True", "False", and "17".</p>

<p>One student answers every question with the answer $17$ and gets a score of zero. The remaining students are each assigned a clause. For every positive literal $x$ occurring in the clause, the student answers the question about $x$ with the answer "True". For every negative literal $\neg x$ occurring in the clause, the student answers the question about $x$ with the answer "False". For every other question, the student answers $17$. Every such student gets a score of one.</p>

<p>An answer key must correspond with an assignment of binary values to the variables (since no question has $17$ as the correct answer as shown by the fact that the student who always answered $17$ got zero points). Furthermore, there must be exactly one true literal in each clause under this assignment in order for the answer key to match the scores given to the students. In other words, the satisfying assignments to the input 1-in-3 SAT formula are in a bijection with the answer keys consistent with the student scores.</p>

<p>Clearly then, deciding whether an answer key consistent with the student scores exists is NP-hard. Similar arguments can be made to show that for example counting answer keys is #P-complete.</p>

CC BY-SA 3.0
2017-06-28T23:51:32.720Z
Thanks for answering! I had realized the similarity to SAT, but hadn't realized this reduction.
James Dong
CC BY-SA 3.0
2017-06-28T21:30:49.847Z
2017-06-28T21:30:49.847Z
Mikhail Rudoy
<p>Consider multiple students taking a multiple-choice tests. The test has $q$ questions, and each question has $m$ choices. ($q$ can be large, but $m$ is rather small.) You are given $n$ tests, complete with all answer choices and their grades (number of questions correct). Find the set of answers keys which produce these scores.</p>

<p>I and a few friends had a go at it, but I was wondering if there was an efficient algorithm to solve this.</p>

<ds.algorithms><optimization>
Finding an answer key given tests and scores
James Dong
# Finding an answer key given tests and scores

(Asked by: username_0 on 2017-06-28)

Consider multiple students taking a multiple-choice tests. The test has $q$ questions, and each question has $m$ choices. ($q$ can be large, but $m$ is rather small.) You are given $n$ tests, complete with all answer choices and their grades (number of questions correct). Find the set of answers keys which produce these scores.

I and a few friends had a go at it, but I was wondering if there was an efficient algorithm to solve this.

**Tags:** ds.algorithms, optimization


---

## 1 answers

### Answer by username_1 on 2017-06-28. Score: 1 | Accepted answer

Solving this problem is NP-hard. In particular, even deciding whether there exists an answer key consistent with the given answer choices and scores is NP-complete. We can prove this by reduction from 1-in-3 SAT.

Given a 1-in-3 SAT formula with $c$ clauses and $n$ variables, we construct an instance of your problem with $n$ questions, each with 3 choices, and $c+1$ sample answer/grade pairs.

For each variable $x$, one of the questions is "what is the value of boolean variable $x$?" and the three possible answers are "True", "False", and "17".

One student answers every question with the answer $17$ and gets a score of zero. The remaining students are each assigned a clause. For every positive literal $x$ occurring in the clause, the student answers the question about $x$ with the answer "True". For every negative literal $\neg x$ occurring in the clause, the student answers the question about $x$ with the answer "False". For every other question, the student answers $17$. Every such student gets a score of one.

An answer key must correspond with an assignment of binary values to the variables (since no question has $17$ as the correct answer as shown by the fact that the student who always answered $17$ got zero points). Furthermore, there must be exactly one true literal in each clause under this assignment in order for the answer key to match the scores given to the students. In other words, the satisfying assignments to the input 1-in-3 SAT formula are in a bijection with the answer keys consistent with the student scores.

Clearly then, deciding whether an answer key consistent with the student scores exists is NP-hard. Similar arguments can be made to show that for example counting answer keys is #P-complete.

> **Comments:**
> **username_0**: Thanks for answering! I had realized the similarity to SAT, but hadn't realized this reduction.  

---

