1 of 43

CS 10

Limits of computing

2 of 43

Today’s agenda

  • Complexity overview
  • Tractable vs intractable problems
  • P vs NP
  • Halting problem
  • Decidability and computability
  • Takeaways

3 of 43

Complexity

4 of 43

How fast is a program?

  • Use a timer
    • Different machines might have different specs
  • Instead, measure by number of operations
    • Results are given with regards to the size of the input (often denoted as n)

​

  • Big O notation
    • Upper bound on performance (runtime), denoted as a function of input size
    • Also called order of growth or asymptotic analysis

5 of 43

Examples

Big O notation

Name

Example

O(1)

constant

Pick first element of a list

O(log(n))

logarithmic

Use binary search to find an element in a sorted list

O(n)

linear

Read a file’s contents

O(n log(n))

superlinear1

Sort a list2

O(nc) [e.g. n2]

polynomial

Introduce everyone to everyone else

O(cn) [e.g. 2n]

exponential

Recursive Fibonacci

  1. technically, superlinear is anything worse than linear, but it’s widely used this way (worse than linear, better than polynomial)
  2. using a comparison-based sorting algorithm

6 of 43

Example: exponential function

Running this with n = 100 didn’t finish before these slides were written (6+ hours)!

Each call makes 2 more calls (we say this has a “branching factor” of 2)

This is O(2n)

7 of 43

Just how bad is it?

8 of 43

Today’s agenda

  • Complexity overview
  • Tractable vs intractable problems
  • P vs NP
  • Halting problem
  • Decidability and computability
  • Takeaways

9 of 43

Tractability

10 of 43

Tractable vs intractable

  • Very simply put, tractable is polynomial or better
    • everything else is intractable (foreshadowing: some things are worse than intractable)
  • Tractable = “fast”, intractable = “slow”?
    • The quotes do a lot of heavy lifting here!
    • Practically, even quadratic runtime can be too slow
    • Similarly, if your input size is bounded to a small n (think less than 10), an exponential solution might be acceptable

11 of 43

Intractable problems

  • Let’s revisit our exponential program:
    • Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2) is O(2n)
    • Is computing fibonacci numbers an intractable problem?
  • There is more than one way to solve a problem! Always try to optimize your program’s runtime

12 of 43

Today’s agenda

  • Complexity overview
  • Tractable vs intractable problems
  • P vs NP
  • Halting problem
  • Decidability and computability
  • Takeaways

13 of 43

P vs NP

14 of 43

Solution vs verification

  • Consider a program that finds a solution to a given problem

​

  • How long does it take to find a solution?
    • i.e. how long does it take for the program to run?
  • How long does it take to verify a solution?

15 of 43

Example: Where’s Waldo

Finding a solution:

  • scan the picture (sliding “waldo-sized” window)
  • if Waldo is in our window, highlight him!

16 of 43

Example: Where’s Waldo

Verifying a solution:

  • is that Waldo in the window?

Finding a solution is slow, but verifying a solution is fast

Aside: doing assignments vs grading assignments…?

17 of 43

Another example

Write a program to find the dumbest reddit post

  • How can you verify the post returned is in fact the dumbest one?

Here, finding a solution and verifying a solution are both slow

​

​

Note: both these examples are tractable (technically)

  • in practice, scraping the entirety of reddit is quite slow (and you’ll likely get rate limited or outright IP banned; not speaking from personal experience here at all)

18 of 43

P vs NP

  • P (Polynomial time)
    • able to find a solution in polynomial time
  • NP (Nondeterministic Polynomial time)
    • able to verify a solution in polynomial time
  • P is in NP
    • you can always verify a solution in P by finding the solution yourself
    • Aside: “in P” and “NP” is easy to distinguish in text, but hard to do so in speech

19 of 43

The knapsack problem

Given a bag with a set capacity, and several items with both size and value:

  • How can you maximize the value in your bag?

Naive solution: just try every possible configuration

  • Finding a solution is slow
  • Verification is also slow

To make this an NP problem, we need to rephrase the question:

  • Is there a way to fill the bag (without overflowing) that has value at least V?

20 of 43

P vs NP

  • Are there problems in NP that are not in P?
    • Knapsack kind of feels like an example, doesn’t it?
  • To help answer this question, we need a new tool, reduction

21 of 43

Reduction

[tldr] If you have something that can solve B, can you use that to solve A?

​

More formally, A reduces to B means:

  • B is “at least as hard” as A
    • Aside: this term is unintuitive! (to me, at least)
      • in english, “reduce” implies the result is “less”
      • but in math, you reduce to something “harder”
  • Equivalent to saying: A is “no harder than” B

22 of 43

Reduction example

If you have a program that can square a number, can you write a program to cube a number?

Formally:

  • Problem A: for a given x, compute x3
  • Problem B: for a given x, compute x2

Reduce A to B

“Mathy” way to show that cubing something is “no harder than” squaring something

Can you also reduce B to A?

  • In this case, yes!
  • When this happens, both problems are said to have the same complexity

23 of 43

P vs NP

Time for some hand-waving:

  • A problem is NP-Hard if you can reduce it to a known NP-Hard problem
    • If this definition feels self-referential and confusing, that means you’re paying attention!
  • A problem is NP-Complete if it is in NP and NP-Hard

For the sake of today:

  • NP-Complete consists a bunch of problems that all reduce to each other
    • If you find a solution to any of them, you can solve any of the other ones!
    • There is currently no known polynomial-time way to find a solution for any of them
    • Knapsack is in NP-Complete
  • You’ll learn this more formally in CS 70, CS 170, and CS 172, promise!

24 of 43

P vs NP

  • Are there problems in NP that are not in P?
    • Implicitly, we are asking if P = NP
  • If P = NP, all problems in NP are NP-Complete
  • If P ≠ NP, there exist problems in NP that are not in P
  • This is a huge unsolved problem!

25 of 43

P vs NP, in conclusion

20

(oops)

26 of 43

Today’s agenda

  • Complexity overview
  • Tractable vs intractable problems
  • P vs NP
  • Halting problem
  • Decidability and computability
  • Takeaways

27 of 43

The halting problem

28 of 43

The halting problem

For a program P with input I, does this program halt?

  • That is, does the program finish, or does it run forever?

Let’s denote this as halt(p, i), which outputs “true” or “false”

​

Spoiler: halt does not exist

29 of 43

Proof by contradiction

  • Assume we have some function halts that solves the halting problem
  • Let’s define a new function, halts_on_self:
    • halts_on_self(x) returns the result of halts(x, x)
    • Note: both programs and inputs can be represented as strings
  • Now let’s consider this function:

​

What does halts_on_self(broken) do?

30 of 43

The halting problem

  • This is an example of an undecidable problem
  • In fact, any “non-trivial” property about the behavior of a program is undecidable! (Rice’s theorem)
    • To prove this, think about how you might modify the contradiction proof for the halting problem

​

  • Does this mean you can never tell if a program will halt?
    • No! It means there is no solution that works for any program

31 of 43

Today’s agenda

  • Complexity overview
  • Tractable vs intractable problems
  • P vs NP
  • Halting problem
  • Decidability and computability
  • Takeaways

32 of 43

33 of 43

Decidability and computability

34 of 43

Decidability vs computability

Decidability and computability talk about different classes of problems

  • Decidability is for decision problems, whose answer is “yes” or “no”
    • example: is there a path from point A to point B?
  • Computability is for general problems, whose answer is a specific solution
    • example: what is the path from point A to point B? answer “none” if none exists

It’s usually easy to convert between decision problems and general problems

  • Formally, decidability and computability refer to different things, but most of the time, these terms are interchangeable

35 of 43

Today’s agenda

  • Complexity overview
  • Tractable vs intractable problems
  • P vs NP
  • Halting problem
  • Decidability and computability
  • Takeaways

36 of 43

Takeaways

37 of 43

Takeaways

  • Constant/logarithmic good, linear/polynomial ok, exponential bad
  • Tractable is not necessarily fast (intractable is definitely slow, though)
  • P ?=?≠?? NP
    • P: fast to solve, fast to verify
    • NP-Complete: (probably) slow to solve, fast to verify
  • Many things (even simple things) we want to know turn out to be undecidable
  • Just because something is undecidable doesn’t mean you can’t do anything
    • Solutions to the halting problem exist for specific programs (just not generally)
    • Approximations are still valuable
      • Everyone loves compilers
      • Things like dynamic programming have “solved” knapsack for most practical purposes

38 of 43

Today’s agenda

  • Complexity overview
  • Tractable vs intractable problems
  • P vs NP
  • Halting problem
  • Decidability and computability
  • Takeaways

39 of 43

Memes to end the day

Approximation to “does P = NP?”:

  • “Probably not”

40 of 43

Memes to end the day

41 of 43

Memes to end the day

42 of 43

Memes to end the day

43 of 43

Memes to end the day

“Some engineer out there has solved P=NP and it's locked up in an electric eggbeater calibration routine.”