Working Through Cohen's Computer Theory Solutions
I spent three semesters wrestling with this material, mostly because the proof-heavy sections of Daniel Cohen's textbook don't exactly hand you the logic on a silver platter. The solution manual isn't a cheat code, but knowing how to use it properly saves you from spinning your wheels for hours on automata constructions or reducibility proofs. What you're looking at is a companion resource to Cohen's textbook, which covers formal languages, Turing machines, decidability, and complexity theory. The solutions walk through the odd-numbered problems in detail, though some editions include even-numbered ones too depending on where you get it. I'll be honest about the quality upfront: these solutions are better than most academic solution manuals, but they still skip steps that seem obvious to the author and completely opaque to someone seeing the material for the first time. The practical way to use it is this. Attempt the problem yourself first. Not a quick glance. Actually sit down and try the construction or proof. Then open the solution and compare your approach, not just your final answer. The value is in seeing how a different method unfolds, especially for things like pumping lemma applications or non-deterministic to deterministic automaton conversions. When you copy the solution without working it first, you learn nothing and waste your time.
One specific edge case that trips people up constantly involves the state-minimization proofs for DFAs. The textbook asks you to prove minimality using the theorem that two states are equivalent if and only if they produce the same output for all input strings. The solution manual walks through the standard table-filling algorithm, but it glosses over a detail I ran into during an exam: when two states are merged, you have to re-index every transition that pointed to them. I spent twenty minutes on one problem because I didn't realize I needed to update those transition tables after merging, and the book's solution just showed the final diagram without explaining that step. My workaround was to write out the full transition table on scratch paper before and after each merge, then cross-check against the final diagram. Slow, but it made the logic clear. Here's something beginners consistently miss about reducibility proofs. People treat them like templates you can fill in, but the direction of the reduction matters more than the algebra. If you're reducing problem A to problem B, you're showing that solving B lets you solve A. Swap the direction and your entire proof falls apart. The solution manual gets this right in most cases, but there's a section on NP-completeness where the reduction from 3-SAT to CLIQUE is presented in a way that makes it look like the mapping is arbitrary. It isn't. The variables become vertices, clauses become triangles, and the edge construction follows a specific rule about connecting literals that appear in different clauses. I've seen students draw edges between every pair of vertices in a clause instead of just between literals in different clauses, which breaks the correctness argument. The corrected approach maps each literal occurrence to its own vertex and only connects vertices representing literals from distinct clauses that aren't negations of each other. Another thing worth noting is that the computability section, particularly around diagonalization and the halting problem, has solutions that are technically correct but written at a level that assumes you already understand the underlying recursion theory. If you're reading this as your first exposure, expect to slow down. Spend more time on the definitions of partial recursive functions and the difference between decidable and recognizable languages than the problems themselves. The problems are where you apply the definitions, and if the definitions are fuzzy, the applications won't land.
Complexity classes get hand-wavy in places. The textbook and solution set handle P versus NP adequately for an introductory course, but they don't dig deep enough into Ladner's theorem or the collapse scenarios that would follow from certain breakthroughs. If you want a more complete picture, pairing Cohen with Sipser's treatment of the same topics fills gaps, though Sipser also leaves some things implicit. If you're looking to download a copy, the official route is through your university library or the publisher's website. Be cautious about sites offering free PDFs, since many of those circulating online are outdated editions with errors from early printings. The second edition corrected several mistakes present in the first, particularly around the Gödel incompleteness coverage and the exercises on context-free grammars. Make sure you're cross-referencing to the right edition number when checking solutions. The solutions manual works best alongside a study group where someone is pushing back on each step. You'll catch gaps in reasoning faster that way than working solo. That's been my experience at least.
Get the Full Details
