sec hard problems figure the graph generated from boolean expression ( + )*( ( literals from the first clause are labeled and literals from the second clause are labeled there is an edge between every two pairs of vertices except when both vertices represent instances of literals from the same clauseor negation of the same variable thusthe vertex labeled does not connect to the vertex labeled (because they are literals in the same clauseor the vertex labeled (because they are opposite values for the same variablecoping with -complete problems finding that your problem is -complete might not mean that you can just forget about it traveling salesmen need to find reasonable sales routes regardless of the complexity of the problem what do you do when faced with an -complete problem that you must solvethere are several techniques to try one approach is to run only small instances of the problem for some problemsthis is not acceptable for exampletraveling salesman grows so quickly that it cannot be run on modern computers for problem sizes much over citieswhich is not an unreasonable problem size for real-life situations howeversome other problems in pwhile requiring exponential timestill grow slowly enough that they allow solutions for problems of useful size consider the knapsack problem from section we have dynamic programming algorithm whose cost is th(nkfor objects being fit into knapsack of size but it turns out that knapsack is -complete isn' this contradictionnot when we consider the relationship between and how big is kinput size is typically ( lg kbecause the item sizes are smaller than thusth(nkis exponential on input size