Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
sav08:homework03 [2008/03/06 18:59] vkuncak |
sav08:homework03 [2008/03/06 19:06] vkuncak |
||
|---|---|---|---|
| Line 22: | Line 22: | ||
| in conjunctive normal form. You do not need to use any deep results of complexity theory. | in conjunctive normal form. You do not need to use any deep results of complexity theory. | ||
| - | Specifically, prove that there exists an infinite family of formulas $F_1, F_2,\ldots$ such that for each $n$ //any// algorithm that transforms $F_n$ to CNF needs exponential time. (Note that it is not enough to prove that one particular algorithm will take exponential time, you need to prove that every algorithm would need exponential time.) | + | Specifically, prove that there exists an infinite family of formulas $F_1, F_2,\ldots$ such that for each $n$, //every// algorithm that transforms $F_n$ to CNF needs exponential time. (Note that it is not enough to prove that one particular algorithm will take exponential time, you need to prove that every algorithm would need exponential time.) |
| ===== Problem 4: NAND ===== | ===== Problem 4: NAND ===== | ||