1	Problems and Solutions Computers and Formal Languages Computers Solving Problems with Formal Languages
2	PROBLEM
3	Abu Ja’Far Muhammad ibn-Musa Al Kowhrismi
4	Kinds of problems for which we seek solutions Decision One Solution Map to {0,1} Function One Solution Optimization problems are a subset Enumeration Difference between a solution and a complete solution Instance vs set of instances
5	Kinds of problems By and large, we will focus only on decision problems. Function problems and optimization problems can be re-formulated as decision problems We base our entire theory of complexity on decision problems Decidability is a natural bridge between solutions and computers as acceptors of formal languages We will consider enumeration problems only in the context formal languages as we consider the ultimate power of the Turing Machine in accepting recursively enumerable languages
6	Solutions WHAT IS A SOLUTION? Concrete notion: Algorithm results in a decision {0,1} Restated: Problem is decidable Abstract notion in context of a computer: Solution: Enter an accepting state and HALT No solution: Never HALT given infinite time
7	A non-decidable problem Turing: The Halting Problem The input is itself a program which sets the output to false if its input is true
8	Complexity of a problem/solution Must put an upper and lower bound on the complexity Complexity can be expressed in time or space, and the two are interchangeable
9	Complexity Let n be the size of the problem and a be a constant Polynomial complexity n^a Exponential complexity aⁿ
10	Complexity Problems that require Polynomial time/space to solve are said to be tractable However there may be instances which, although the complexity is polynomial, require practically infinite time to solve Problems that require Exponential time/space to solve are said to be intractable There may be instances that can be solved in non-infinite time Solve x=aⁿ for n=3
11	Complexity There are problems which are at first blush apparently exponential, but algorithmic efficiency and cleverness allows a (complete!) solution in polynomial time Align two strings There are problems which are normally exponential, and for which NO POLYNOMIAL SOLUTION has yet been found Align n (>2) strings
12	Computational Complexity- Solvable (tractable) problems Find the sum of 2 numbers Find the sum of 20 numbers Find the sum of 37 trillion numbers Same algorithm for all 3 instances, with linear complexity. Would use a DO-loop Can build a more efficient algorithm for #1 (and perhaps #2), specific instances of the problem, but the solution for these specific instances is not generalizable
13	Complexity -Tractable Problems Sometimes efficiency can reduce complexity Linear search O(n) Binary search O(log₂n) The efficiency depends on the instance of the problem, and in some cases, depends on the solution itself Example: If the solution were 1, linear search would be one cycle, where Binary search would take log₂n cycles Here, if we knew the character/scope of the solution set, we could better choose our algorithm
14	Complexity -Tractable Problems Efficiency Improvement: another GREAT example is the FFT Brute force solution (all harmonics, all data points) is O(n²) Special instance of the problem where the number of data points is a power of 2: O(log₂n) Note that both solutions in this case are polynomial, but when the FFT was developed in the era of slow computers, with large n, the gain was substantial In this case we chose the algorithm based on the problem set (ie class of specific instances of the problem)
15	Complexity - Intractable problems Example: Why is this such an difficult example? Because it has been PROVEN that the solution is exponential, and PROVEN that there is no polynomial solution. Many, many problems are NOT PROVEN to be exponential In many problems, including many that we will study relating to Computational Molecular Biology, the problems appear to be exponential, yet there has so far been no polynomial solution found.
16	Complexity - Intractable problems By way of counterexample, consider the alignment of two sequences of symbols, say {A,C,T,G}, which may or may not contain gaps (no symbol in a sequence location - a blank). This is a problem in combinatorics, and the solution promises to be exponential. HOWEVER If there are just two such sequences to align, an efficient algorithm can be written (Needleman-Wunsch) to perform the alignment in polynomial (quadratic, in fact) time.
17	Complexity Consider this problem: f=(AÚB) Ù(-C Ú D) where f,A,B,C,D are Boolean variables. [The size of the problem is 4] Is there an instance where f is true? Solution requires either an enumeration of the instance set consisting of all values of all independent variables (2⁴) and selection an f which satisfies the equation (ie is true) if indeed there is such an f (solution) or a lucky guess.
18	Complexity Suppose that the problem were f=(AÚB) Ù(-C Ú D) Ù(-E) [The size of the problem is now 5] Solution requires either enumeration of all values of independent variables (2⁵) or a lucky guess
19	Complexity
20	Complexity Suppose we did guess… Let’s guess A=t,B=f,C=t,D=f,E=t,G=t Wow! A lucky guess, because instead of enumerating 64 choices, we got it right on one guess (although there are certainly other guesses that would have satisfied) Q. How do we know it is a good guess (verify)? A. Because we had to plug in the values for A,B,C,D,E,G and evaluate f Q How long did that take? A. Polynomial time to verify
21	"So" So, our solution was Non-deterministic (“N”) solution (ie a guess) Verifiable (not the same thing as solvable) in polynomial (“P”) time Thus we have a problem (“Class NP”) which certainly has a nondeterministic proposed solution which can be verified as a correct solution (or not) in polynomial time, BUT we don’t know that the general solution can be found in polynomial time In fact, we have no known algorithm to solve (complete solution) the SAT problem in polynomial time, although it is remotely possible, but highly unlikely, that one may exist.
22	Class NP We will take this problem SAT to be the quintessential representative of the class NP There are other problems which can be formally mapped into SAT in polynomial time. This mapping is 1-2 and called a polynomial reduction. A polynomial composed with a polynomial is a polynomial, so … If SAT can be shown to have a polynomial solution, then these other problems which can be reduced to SAT in polynomial time will also have polynomial solutions ( by composition of functions) Any of these can be mapped to another, and by composition of functions, ultimately to SAT, also in polynomial time
23	NP-completeness The class of NP problems which appear to be the most difficult ie are at least as difficult an any others ie are problems to which other NP problems reduce in polynomial time are called NP-complete problems Restated: xÎNP yÎNP y £_px
24	NP-Complete problems So, what are these NP Complete problems (problems which can be mapped into SAT or any other NP-Complete problem in polynomial time)? Map Coloring Problem Traveling Salesman Problem (TSP) Bin Packing Problem Knapsack problem Hamiltonian Graph Problem
25	NP-hard Problems There is yet another group of problems that are not in the class class NP, yet have polynomial reductions to NP-complete problems. These are said to be NP-hard. By and large, combinatorial problems, and particularly combinatorial optimization, are NP hard problems. In this course, we will deal with many combinatorial problems which look to be exponential, ie NP-hard problems. Very few will turn out to have polynomial solutions, but we will always look for them as we go
26	NP-hard problems and reality So, what are we going to do when confronted with an NP-hard problem? If the instance is of small size, we may solve it We may seek an heuristic solution ¢euristikoV
27	HEURISTICS An heuristic is a way to get an approximate answer to a hard problem, or even to get an exact answer most of the time. Note that an heuristic itself yields an exact solution in polynomial time, but the problem being solved is different from the original problem. Restated: An heuristic rephrases the original problem and solves the rephrased problem. It is a cleverly devised alias that yields an equivalent solution to the ‘real’ problem most of the time.
28	Computers and Formal Languages We solve problems using a computer, which is governed by a program (algorithm). The program is an instance of a formal language. If the computer accepts the language instance, and if it halts (it may not) given this input, then it has decided the problem, and will yield a true or a false. If the algorithm is correct, and the decision is true, it has solved the problem
29	Computer Models Key Concept : specific computers (sci computer models, idealized computers, abstract machines) accept certain languages. The ability to solve problems is governed by the complexity of the computer and the characteristics of the language it accepts.
30	Interplay between a computer and a solution What is a computer? The abstract computer depends on the problem We reach a limit of design of abstract computers beyond which we cannot devise a better computer (Church-Turing conjecture)