ALGORITHMS AND COMPLEXITY
Click on Insert > new slide to choose your cover, then delete this page.
Week 2: Computational Complexity
Cat Kutay
Click on Insert > new slide to choose your cover, then delete this page.
Reference
• See Chapter 3 in text. • For another similar approach see Drozdek Ch2
library site • Computers and Intractability , A guide the Theory of
NP-Completeness, Garey and Johnson, W.H.Freeman and Company, New York, 1979. • Algorithms and Complexity, Second Edition, Herbert
S. Wilf, AK Peter Ltd Canada, 2002. • The Nature of Computation, Christopher Moore and
Stephan Mertens, Oxford University Press, 2011
Click on Insert > new slide to choose your cover, then delete this page.
Meet some Ancestors
• Abu Ja’far Mohammed ibn Mûsâ al-Khowârizmî was a Persian mathema=cian (ca. 780–850) who wrote a book that was the founda=on of algebra and algorithms
• Alan Turing, developed Computer Science - Please watch the You tube by Cambridge University 8 min "Alan Turing - Celebra=ng the Life of a Genius" The HIT220 resources page also contains links to you tubes about Turing, Turing Machines and the Hal=ng Problem.
• Leonard Euler, The Father of Graph Theory was one of the most prolific mathema=cians of all =me. Worth at look around about his contribu=ons to mathema=cs and science but en=rely op=onal.
• Euclid developed Geometry. We studied the Euclidean Algorithm last week however Euclid is more famous for his 5 postulates. Euclid's Book/s "The Elements" is the most published book of all =me. Beyond Geometry, Euclid proved many results in number theory which we love to use. The Fundamental Theorem of Arithme=c says that every posi=ve integer greater than 1 has a unique prime decomposi=on. So useful for finding GCD, LCM, simplifying frac=ons.
• Ada Lovelace developed the first computer algorithm to calculate Bernoulli numbers
Click on Insert > new slide to choose your cover, then delete this page.
Computational Complexity
“As soon as an Analytic Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will arise – By what course of calculation can these result be arrived at by the machine in the shortest test time?”
Charles Babbage (~1864)
http://www.cbi.umn.edu/about/babbage.html
“A wide variety of commonly encountered problems from mathematics, computer science, and operations research are known to be NP-complete …..
it is important for anyone concerned with the computational aspects of these fields to be familiar with the meaning and implications of this concept.”
Garey & Johnson, 1978
Click on Insert > new slide to choose your cover, then delete this page.
In defining a measure of efficiency
• The efficiency of execution of an algorithm depends on the hardware, programming language used, compiler, programming skill, etc. These variables are not useful for measuring efficiency of an algorithm.
• A computing time for millions of bits of input data can be expected to take longer than one where a small amount of input is required.
• To evaluate an algorithm’s efficiency, logical time units that express a relationship between the size of an input and the amount of time and space required to process the input should be used.
• Desirable scaling property – When the input size doubles, the algorithm should only slow down by some constant factor.
Click on Insert > new slide to choose your cover, then delete this page.
Analysis of Algorithms
• Analysis of an algorithm gives insight into how long the program runs and how much memory it uses • time complexity • space complexity
Click on Insert > new slide to choose your cover, then delete this page.
Complexity Analysis
• The same problem can frequently be solved with different algorithms which differ in efficiency. Or choice of data structure – e.g. Linked list vs array
• Time is generally the most important • Space (memory) • Tradeoffs between time and space complexity • Type of measurement
1. Worst-case 2. Best- case 3. Average-case
• Generally concerned with worst case analysis. We also study best case but will usually skip average case analysis.
• Worst case analysis provides a running time guarantee for all inputs.
Click on Insert > new slide to choose your cover, then delete this page.
Computational Complexity
• The computational complexity of an algorithm is measure of how many steps the algorithm will require in the worst case for an instance or input of a given size. Most commonly used notation for describing asymptotic complexity is “big oh" or "big O" notation (O for order of the complexity). • Very loosely, this notation strips away the less
significant calculations to give the magnitude of the number of operations for a large input size.
Click on Insert > new slide to choose your cover, then delete this page.
Experimental Analysis and Challenges
• One way to study the efficiency of an algorithm is to implement it and experiment by running the program on various test inputs while recording the time spent during each execution.
• While experimental studies of running times are valuable, especially when finetuning production-quality code, there are three major limitations to their use for algorithm analysis:
1. Experimental running times of two algorithms are difficult to directly compare unless the experiments are performed in the same hardware and software environments.
2. Experiments can be done only on a limited set of test inputs; hence, they leave out the running times of inputs not included in the experiment (and these inputs may be important).
3. An algorithm must be fully implemented in order to execute it to study its running time experimentally (most serious drawback).
Click on Insert > new slide to choose your cover, then delete this page.
Moving Beyond Experimental Analysis
The goal is to develop an approach to analysing the efficiency of algorithms that: 1. Allows us to evaluate the rela_ve efficiency of
any two algorithms in a way that is independent of the hardware and so`ware environment.
2. Is performed by studying a high-level descrip_on of the algorithm without need for implementa_on.
3. Takes into account all possible inputs.
Click on Insert > new slide to choose your cover, then delete this page.
Counting Primitive Operations
To analyse the running time of an algorithm without performing experiments, we perform an analysis directly on a high-level description of the algorithm.
We base the description on a set of primitive operations such as the following: 1. Assigning a value to a variable
2. Following an object reference
3. Performing an arithmetic operation (i.e. adding two numbers)
4. Comparing numbers
5. Accessing a single element of an array by index
6. Calling a method
7. Returning from a method
Click on Insert > new slide to choose your cover, then delete this page.
Primitive Operations
• This operation count will correlate to an actual running time in a specific computer, for each primitive operation corresponds to a constant number of instructions, and there are only a fixed number of primitive operations. • The implicit assumption in this approach is that the
running times of different primitive operations will be fairly similar. Thus, the number, t, of primitive operations an algorithm performs will be proportional to the actual running time of that algorithm.
Click on Insert > new slide to choose your cover, then delete this page.
Measuring Operations as a Function of Input Size
• To capture the order of growth of an algorithm's running time, we will associate, with each algorithm, a function f(n) that characterizes the number of primitive operations that are performed as a function of the input size n.
• Later today we will introduce the most common functions that arise, and introduce a mathematical framework for comparing functions to each other.
Click on Insert > new slide to choose your cover, then delete this page.
Classifica?on - Seems useful
• An algorithm is deemed efficient if it has a polynomial running time (e.g. f(n)=n2).
• Polynomial time classification typically exposes or indicates the existence of “essential structure”.
• When there are high constants and/or exponents, over a period of time improved algorithms are often discovered.
• Exceptions – some polynomial time algorithms are not (practically) efficient.
Click on Insert > new slide to choose your cover, then delete this page.
Worst Case Analysis is main focus
• Running time guarantee for any input size. • Some algorithms of exponential time complexity are
successful/practical because the worst case occurs rarely. • Best Case Analysis • Average case analysis (typically complex
calculations) • Amortized Complexity – Sections 5.3 Textbook. Read
about it so that you could discuss the idea.
Click on Insert > new slide to choose your cover, then delete this page.
The order of a nested loop
𝑠 ≔ 0 for 𝑖 ≔ 1 to 𝑛
for j ≔ 1 to 𝑖 𝑠 ≔ 𝑠 + 𝑗 * (𝑖 − 𝑗 + 1)
next 𝑗 next 𝑖
Exercise: Count the number of operations which are additions, subtractions, multiplication.
Click on Insert > new slide to choose your cover, then delete this page.
Counting elementary operations
• What is classified as an “elementary operaLon” may vary. E.g. Drozdek focuses on counLng the number of assignments(eg changing values in memory) rather than operaLons.
• Given an algorithm to evaluate a polynomial, the crucial issue is the number of addiLons and mulLplicaLons needed whereas the number of comparisons may be the most important in a search of a list.
• Elementary operaLons may include addiLon, subtracLon, mulLplicaLon, division and comparison.
Click on Insert > new slide to choose your cover, then delete this page.
𝑠 ≔ 0 for 𝑖 ≔ 1 to 𝑛
for j ≔ 1 to 𝑖 𝑠 ≔ 𝑠 + 𝑗 * (𝑖 − 𝑗 + 1)
next 𝑗 next 𝑖
• Number of calculations is:
• Order of complexity:
𝑓 𝑛 = 2𝑛! + 2𝑛 = 𝑶(𝒏𝟐)
• There are two additions, one multiplication and one subtraction for each iteration of the inner loop. i.e. 4 operations per iteration of inner loop.
• Inner loop executes when: 𝑖 = 1,𝑗 = 1 𝑖 = 2,𝑗 = 1,2 𝑖 = 3,𝑗 = 1,2,3
⋮ 𝑖 = 𝑛,𝑗 = 1,2,3,…,𝑛
4 1 + 2 + ⋯+ 𝑛 = 4∑!"# $ 𝑖 = %$($'#)
) = 2𝑛 𝑛 + 1 = 2𝑛) + 2𝑛
Click on Insert > new slide to choose your cover, then delete this page.
Which is the simplest rising function that is bigger than f(n) From Drozdek
Click on Insert > new slide to choose your cover, then delete this page.
Func?on growth and complexity
• Function growth • Big-O notation • Tractability • Polynomial growth • Exponential growth • Execution times
Click on Insert > new slide to choose your cover, then delete this page.
Growth Functions
Different functions can effect numbers, and how the growth can happen rapidly.
Smallest to Greatest
O(1), log2(n), n, (n)log2(n), n2, 2n , n!
Consider N=10 0(1) = 1 log2 (10)= 3.32 10 10 log2 (10)= 33.32 102= 100 210= 1024 10!= 3,628,800
Click on Insert > new slide to choose your cover, then delete this page.
Evaluating
Click on Insert > new slide to choose your cover, then delete this page.
Asymptotic complexity
• In algorithm analysis, we focus on the growth rate of the running time as a function of the input size n, taking a "big-picture" approach. For example, it is often enough just to know that the running time of an algorithm grows proportionally to n.
• The asymptotic complexity is the limiting behaviour of the execution time of an algorithm when the size of the problem goes to infinity.
• This is usually denoted in big-O notation. • Definition: A theoretical measure of the execution of an algorithm, usually the
time or memory needed, given the problem size n, which is usually the number of input items.
Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n).
Click on Insert > new slide to choose your cover, then delete this page.
Asympto>c complexity – an example
The "big-O" notation estimates the rate of growth of a function, for “large” n.
f (n) = n2 + 100n + log10n + 1,000 = O(n2) " f (n) is big-oh of n squared ”
The order of complexity of f (n) is a polynomial function (quadratic)
Figure 2-1 (Drozdek) The growth rate of all terms of function f (n) = n2 + 100n + log10n + 1,000
Click on Insert > new slide to choose your cover, then delete this page.
Function growth within polynomial time
• lg n is base 2 logarithm • Orders of magnitude:
O(1) constant O(log n) logarithmic
O(n) linear O(n log n) O(n2) quadratic
O(n3) cubic Note axis scale
Figure 2-5 (of Drozdek) Typical functions applied in big-O estimates
Click on Insert > new slide to choose your cover, then delete this page.
Rescaling of time axis
Image source Moore & Mertens
Click on Insert > new slide to choose your cover, then delete this page.
Execution time (workshop)
Figure 2-4 (Drozdek) Classes of algorithms and their execution times on a computer executing 1 million operations per second (1 sec = 106 μsec (microseconds) = 103 msec (milliseconds))
Click on Insert > new slide to choose your cover, then delete this page.
Big-O notation
Formal Definition:
f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k.
The values of c and k must be fixed for the function f and must not depend on n.
Click on Insert > new slide to choose your cover, then delete this page.
Big-O notation – the definition
f(n) is O(g(n)) if there exists numbers c, N > 0
such that for each n ≥ N
f(n) ≤ c·g(n)
The meaning: • f(n) is larger than g(n) only for finite number of n’s • a constant c and a value N can be found so that for every value of n ≥ N
f(n) ≤ c·g(n) (such c and the N are called witnesses) • f(n) does not grow more than a constant factor faster than g(n)
We may write f(n) = O(g(n)) but the “=“ does not represent genuine equality. We say that f(n) is O(g(n)), (because O(g(n)) is a collection - an infinite set).
Click on Insert > new slide to choose your cover, then delete this page.
Big-O notation: illustration
N
c·g(n)
f(n)
n
f(n) ≤ c·g(n)
n ≥ N
The function f(n) is O(g(n)), since f(n) ≤ c·g(n) when n ≥ N.
Click on Insert > new slide to choose your cover, then delete this page.
What Is Big O? (Comparing Algorithms)
• https://www.youtube.com/watch?v=MyeV2_tGqvw
Click on Insert > new slide to choose your cover, then delete this page.
General rules
• Ignore constants 5n -> 0(n)
• Certain terms ‘dominate’ others O(1) < 0(logn) < o(n), o(nlogn) < o(n2)< o(2n) < o(n!) e.g. ignore low-order terms when they dominated by higher one
X=5+(15*20) ; Independent of input size, N O(1) ‘big O of one’
x=5+(15*20) ; y=15-2; Print x + y
Total time = 0(1) + 0(1) + 0(1) 3* O(1) drop constants O(1)
Click on Insert > new slide to choose your cover, then delete this page.
Cont.
Linear time: for x in range (0,n):
print x; // O(1)
N * O(1) = O(N)
x=5+(15*20) ; //O(1)
for x in range (0,n):
print x;
Total number = O(1) + O(N) = O(N)
In another word, when N gets large, the time it takes to compute Y is meaningless, as the for-loop dominate the run time.
}//O(N)
Click on Insert > new slide to choose your cover, then delete this page.
i :=0; while i<n Do
i=i+1 print i
i :=0;j=0; while i<n Do
i=i+3 j+=1
print j,n-iF(n) = n O(f(n) = O(n)
F(n) = n/3 O(f(n) = O(n)
Click on Insert > new slide to choose your cover, then delete this page.
Quadratic time
for x in range (0,n): for y in range (0,n):
print x*y // O(1) Total number = O(N2)
}//O(N2)
Click on Insert > new slide to choose your cover, then delete this page.
Adding O()
5+(15*20) ;
for x in range (0,n):
print x;
for x in range (0,n):
for y in range (0,n):
print x*y
What is the total runtime ???
Click on Insert > new slide to choose your cover, then delete this page.
O(?)
5+(15*20) ;
for x in range (0,n):
print x;
for x in range (0,n):
for y in range (0,n):
print x*y
What is the total runtime ???
O(N2)
Click on Insert > new slide to choose your cover, then delete this page.
O() of this code with order of each section
If x>0:
// O(I) else if x<0:
//O(logn)
else: //O(n2)
Click on Insert > new slide to choose your cover, then delete this page.
Big-O notation: examples
These functions are O(n2): 3n2 1000n2 + 10000 3n 3n2 + log n + 123
These functions are not O(n2): 3n2.01 3n3
Click on Insert > new slide to choose your cover, then delete this page.
Figure 2-3 Comparison of funcEons for different values of c and N from Figure 2-2 What happens if c=2, when is f(n)<g(n)
Figure 2-2 (Drozdek) Different values of c and N for function f (n) = 2n2 + 3n + 1 = O(n2) calculated according to the definition of big-O
Click on Insert > new slide to choose your cover, then delete this page.
Big O and efficiency
• An algorithm is deemed efficient if it has a polynomial running time i.e. O(nc) where c is a constant.
• Polynomial time classification typically exposes or indicates the existence of “essential structure”.
• When there are high constants and/or exponents, over a period of time improved algorithms are often discovered.
• Exceptions – some polynomial time algorithms are not (practically) efficient.
• More exceptions - Some exponential time algorithms work well in practice because the worst case occurs rarely.
Click on Insert > new slide to choose your cover, then delete this page.
Big-O notation: properties
1. (transitivity) If f(n) is O(g(n)) and g(n) is O(h(n)), then f(n) is O(h(n)) (i.e., f(n) = O(g(n)) = O(O(h(n))) = O(h(n)).
2. If f(n) is O(h(n)) and g(n) is O(h(n)), then f(n) + g(n) is O(h(n)).
3. ank is O(nk). 4. nk is O(nk+j) for any j >= 0. 5. If f(n) = cg(n), then f(n) = O(g(n)). 6. logan = O(logbn) for any numbers a, b > 1. 7. logan is O(log2n) for any positive a ≠ 1
Click on Insert > new slide to choose your cover, then delete this page.
Exercises - workshop
• Use the definiLon of big-O to show that f is O(g) for each of the following funcLons. (i.e. Find the witnesses c and N.) In each case, assume that n is a posiLve integer.
• Remember The func=on f(n) is O(g(n)), since f(n) ≤ c·g(n) when n ≥ N.
a) f(n) = 8n, g(n) = n
We want c and N such that 8n ≤ c × g(n) for all n ≥ N.
With c = 8, N = 1 we have 8n ≤ 8n which is true as required for all n ≥ 1.
Click on Insert > new slide to choose your cover, then delete this page.
(b) f(n) = 4n − 1, g(n) = n We want c and N such that 4n − 1 ≤ c × n for all n ≥ N.
Similarly, try c = 4, N = 1.
4n − 1 ≤ 4n − 1 which is true as required for all n ≥ 1.
(c) f(n) = n2 + 2n + 1, g(n) = n2 (Details in Exercises – workshop slide) 0 ≤ n 2 + 2n + 1 ≤ n 2 + 2n 2 + n2 = 4n2
Hence, c = 4 and N = 1 are witnesses.
(d) f(n) = 2n2 + 5n − 3, g(n) = n2
2n2 + 5n − 3 ≤ 2n2 + 5n2 − 3n2
≤ 4n2 , for n ≥ 1
Hence, c = 4 and N = 1 are witnesses.
(e) f(n) = 457, g(n) = 1 c = 457 and N = 1.
The function f(n) is O(g(n)), since f(n) ≤ c·g(n) when n ≥ N. OR 0 ≤ f(n) ≤ c.g(n) for all n ≥ N
Click on Insert > new slide to choose your cover, then delete this page.
(f) Show that 3n2 + 25 is O(n2) 3n2 + 25 ≤ 3n2 + 25n2 n ≥ 1
3n2 + 25 ≤ 28n2
Hence, c = 28 and N = 1 are witnesses.
(g) Show that 2n2 is O(n3) 2n2 ≤ 2n3
Hence, c = 1 and N = 2 are witnesses.
Click on Insert > new slide to choose your cover, then delete this page.
Click on Insert > new slide to choose your cover, then delete this page.
Exercises - workshop
Click on Insert > new slide to choose your cover, then delete this page.
Relatives of Big-Oh - extension
big-Omega Ω • f(n) is Ω(g(n)) if there is a constant c > 0 and
an integer constant n0 ≥ 1 such that f(n) ≥ c•g(n) for n ≥ n0
big-Theta Θ • f(n) is Θ (g(n)) if there are constants c’ > 0 and
c’’ > 0 and an integer constant n0 ≥ 1 such that c’•g(n) ≤ f(n) ≤ c’’•g(n) for n ≥ n0
Click on Insert > new slide to choose your cover, then delete this page.
TSP – Travelling salesman problem
• Below link, solves the problem for however many ciaes you want to select by trying out all possible routes, and recording the best so far. You can get a feel for what an intractable problem looks like by seeing how long the interacave takes to solve the problem for different size maps
hdps://csfieldguide.org.nz/en/interacaves/city-trip/
Stop, set up ciaes then start
From hHps://csfieldguide.org.nz/en/chapters/complexity-and-tractability/whats-the-big-picture/
Click on Insert > new slide to choose your cover, then delete this page.
Tractability - overview
• The area of tractability explores problems and algorithms that can take an impossible amount of computation to solve except perhaps for very small examples of the problem.
Tractable – an efficient algorithm. i.e. Polynomial time. Efficient - time complexity is at most a polynomial function of input size. Inefficient: A brute force algorithm or exhaustive search examines every possibility. • For non-trivial problems this approach leads to “combinatorial
explosion” in the number of possibilities. • Unacceptable running time on large inputs. Typically 2n time or worse
for inputs of size n. i.e. Exponential run time. • “Or Worse” - the input size need not be very large at all to generate a
running time well beyond the lifetime of the universe.
Click on Insert > new slide to choose your cover, then delete this page.
Really hard problems
A problem is intractable in the strongest sense if the problem is undecidable. i.e. No algorithm is possible. Read about Russel’s Paradox, and Turing’s Halting Problem.
Another strong sense of intractability occurs when the running time to output a solution to a problem is excessive.
Click on Insert > new slide to choose your cover, then delete this page.
P vs. NP and the Computational Complexity Zoo
https://www.youtube.com/watch?v=YX40hbAHx3s
Many examples in this video are not decision problems, so do not use such problems as examples in your assignments
Click on Insert > new slide to choose your cover, then delete this page.
Decision problems
• In HIT220 you only look at decision problems
• These are yes-or-no question on an infinite set of inputs. The classification of computational complexity classes (e.g. P, NP,NPC) is based on decision problems.
Click on Insert > new slide to choose your cover, then delete this page.
Class P
• A deterministic algorithm is a uniquely defined (determined) sequence of steps for a particular input. There is only one way to determine the next step that the algorithm can make.
• A problem belongs to the class P of decision problems if it can be solved in polynomial time with a deterministic algorithm.
• Two members of P: Graph 2-colourability Is G Eulerian?
The bridges of Königsberg problem solved by Euler in 1736.
Click on Insert > new slide to choose your cover, then delete this page.
The Seven Bridges of Königsberg
https://www.youtube.com/watch?v=f-Zy1q9XFQE
Click on Insert > new slide to choose your cover, then delete this page.
• The graph of the Bridges of of Königsberg has 4 vertices (land) and 7 edges (representing the bridges).
• One could solve the problem using “Brute Force”. An exhaustive search of all possibilities. Exponential time complexity.
• Euler’s insight: In order to cross each edge once, any time we arrive at a vertex along one edge, we have to depart on a different edge.
• Hence the degree of a vertex v, that is the number of edges incident to each v , must be even.
Click on Insert > new slide to choose your cover, then delete this page.
Class NP
• A non-deterministic algorithm is an algorithm that can use a special operation that makes a guess when a decision is to be made.
• A problem belongs to the class NP of decision problems if it can be solved by a non- deterministic polynomial time algorithm (on a theoretical machine allowing infinite parallelism).
• The class of NP problems consists of problems with the property that “checking” whether or not a claimed solution is correct can be performed in polynomial time.
• Two members of NP: Graph k-colourability, Is G Hamiltonian?
A Hamiltonian path is a graph path between two vertices of a graph that visits each vertex exactly once. If a Hamiltonian path exists whose endpoints are adjacent, then the resulting graph cycle is called a Hamiltonian cycle (or Hamiltonian cycle).
So to prove that a decision problem is in NP we would only need to show that checking can be performed in polynomial time. i.e. That there is an efficient checking algorithm. (Probably the most useful thinking for HIT220)
Click on Insert > new slide to choose your cover, then delete this page.
• A non-deterministic algorithm can solve a decision problem if there is a path in the decision tree of the algorithm that leads to a “yes” answer; otherwise it would answer “no”.
• If the number of steps in the decision tree path to the affirmative answer is O(nk), where n is the size of the specific problem, the algorithm is considered polynomial.
There are other ways to describe NP, as per Drozdek which is below but I recommend the previous slide.
In HIT220 I suggest a simpler, but equivalent way of discussing class P: After showing that a problem is in NP, we can show membership in class P by describing and analysing an efficient algorithm for determining the Decision Problem. i.e. (1) Show that it is in NP (polynomial time checking algorithm) and then (2) give an algorithm to solve and show that the decision problem itself is O(nk), where n is input size. For example we could do these steps for 2-colourability or Eulerian graph.
Should be clear that, P is a subset of NP. i.e. It is known that every decision problem in P is also in NP. The big unknown is whether or not every problem in NP is also in P. Is it possible that efficient algorithms exist but that we just haven’t found them? Mostly conjectured that P is not equal to NP. See other readings for this week.
Click on Insert > new slide to choose your cover, then delete this page.
Class NPC • A problem is called NP-complete if it is NP and every NP problem can be polynomially reduced to this problem. • Cook 1970 established that SAT (Boolean
satisfiability problem) is in NPC - Cook’s Theorem (Stephen Cook, 1970) Read pages 13,14 of Garey and Johnson. • If every instance of a problem P1 can be reduced,
in polynomial time, to some instance of P2 then P2 is at least as hard as P1. • If there is a polynomial time algorithm for any NPC
problem then every problem in NP can be solved efficiently.
Click on Insert > new slide to choose your cover, then delete this page.
https://www.donkcowan.com/blog/2013/5/13/p-versus-np-complexity-t
Click on Insert > new slide to choose your cover, then delete this page.
• Showing that any problem is in the class NPC means that there is no polynomial time algorithm unless P = NP. • Most in the field think that is unlikely that P = NP.
What do you think? Is it plausible that “Easy to check YES’s” should have “Easy to obtain solutions”? • Our main focus is on awareness of Class NPC and its
implication and developing some ability to recognise types of problems which might be intractable.
Click on Insert > new slide to choose your cover, then delete this page.
About Input size and encoding
• Complexity of a calculation is measured by expressing the running time as a function of some measure of the input data n needed to describe the problem.
• For graph problems, input size n is typically the number of vertices or edges in the graph. Assumption of a reasonable encoding scheme.
• For problems that involve integers such as computing the GCD, n is the number of bits it takes to express these integers. i.e. ln (input) rather than n.
Click on Insert > new slide to choose your cover, then delete this page.
Theoretical perspective
• If the running Lme is at most a polynomial funcLon of the amount of input data then the calculaLon is called “easy”. Otherwise, it is “hard”.
• To show/classify that a computaLon problem is easy it is enough to describe a fast algorithm.
• To prove that a problem is hard means that you would need to prove that it is impossible to find a fast way of solving the problem.
• The fact that a computaLonal problem is classified as hard does not mean that every instance of it has to be hard.
• A problem is hard because we cannot devise an algorithm for which we can give a guarantee for fast performance for all instances.
Click on Insert > new slide to choose your cover, then delete this page.
Decision Problem example
GRAPH k-COLORING
Input: A graph G=(V,E), a positive integer k.
Question: Is G k-colourable?
A graph is k-colourable if its vertices can be assigned colours from a list of k
colours such that no pair of adjacent vertices has the same colour.
Click on Insert > new slide to choose your cover, then delete this page.
GRAPH 2-COLORING
Input: A graph G=(V,E).
Question: Is G 2-colourable?
A polynomial time algorithm is known.
GRAPH k-COLORING
Input: A graph G=(V,E).
Question: Is G k-colourable?
No polynomial time algorithm is known to determine YES or NO for all
instances.
However if given a colouring of the vertices of G, checking whether or not it is a
k-colouring can be executed in polynomial time.