chap limits to computation this dynamic programming algorithm is tractable if the numbers are "reasonable that iswe can successfully find solutions to the problem when nk is in the thousands such an algorithm is called pseudo-polynomial time algorithm this is different from traveling salesman which cannot possibly be solved when given current algorithms second approach to handling -complete problems is to solve special instance of the problem that is not so hard for examplemany problems on graphs are -completebut the same problem on certain restricted types of graphs is not as difficult for examplewhile the vertex cover and -clique problems are -complete in generalthere are polynomial time solutions for bipartite graphs ( graphs whose vertices can be separated into two subsets such that no pair of vertices within one of the subsets has an edge between them satisfiability (where every clause in boolean expression has at most two literalshas polynomial time solution several geometric problems require only polynomial time in two dimensionsbut are -complete in three dimensions or more knapsack is considered to run in polynomial time if the numbers (and kare "small small here means that they are polynomial on nthe number of items in generalif we want to guarantee that we get the correct answer for an pcomplete problemwe potentially need to examine all of the (exponential number ofpossible solutions howeverwith some organizationwe might be able to either examine them quicklyor avoid examining great many of the possible answers in some cases for exampledynamic programming (section attempts to organize the processing of all the subproblems to problem so that the work is done efficiently if we need to do brute-force search of the entire solution spacewe can use backtracking to visit all of the possible solutions organized in solution tree for examplesatisfiability has possible ways to assign truth values to the variables contained in the boolean expression being satisfied we can view this as tree of solutions by considering that we have choice of making the first variable true or false thuswe can put all solutions where the first variable is true on one side of the treeand the remaining solutions on the other we then examine the solutions by moving down one branch of the treeuntil we reach point where we know the solution cannot be correct (such as if the current partial collection of assignments yields an unsatisfiable expressionat this point we backtrack and move back up node in the treeand then follow down the alternate branch if this failswe know to back up further in the tree as necessary and follow alternate branchesuntil finally we either find solution that satisfies the expression or exhaust the