T Naughton, NUIM
Back to SE307 home

Lab 10 - Checking solutions to intractable problems

Measuring the complexity (resources requirements) of problems is one of the most interesting aspects of computational complexity theory. (You have been exposed to algorithmic complexity theory -- measuring the complexity of solutions -- during your data structures courses.) The concept of calculating how difficult it is to check a solution to a problem is one way of gaining insights into the difficulty of that problem. For example, determining who has won a chess game and TSP (travelling salesman problem) are both intractable problems. However, they are not equally intractable. You can check a solution to one efficiently, but not the other.

Given a chess board configuration after a game of chess has finished, and a particular colour, the problem of deciding whether that colour was the winner or not is intractable. However, given a particular tour of a graph, determining if that tour visits exactly each node once and if the total length of the tour is less than or equal to k, can be solved very efficiently.

A problem with similar properties to TSP is the 3-SAT problem.

Problem 10.1 Given an instance of 3-SAT, and a truth assignment, construct a TM to determine if that assignment does satisfy the instance of 3-SAT. The input tape will consist of the truth assignments for four boolean variables (a, b, c, d), separated by a blank, followed by n clauses (n>=1) of the 3-SAT instance (each separated by a blank). For simplicity, you may assume that no variables are negated in the 3-SAT instance. You may also assume that all inputs are syntactically correct. Your machine should output `T' at the end of the input if the 3-SAT instance is satisfied, and `F' otherwise. An input encoded on the TM input tape would look like   TFFT aca bdc dab cbb dca   to which your application should respond with an `F'.

When you are finished, consider competing for SE307 BONUS marks.