CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Limits of Computation

• P vs. NP
  1. Complexity Classes
  2. Solving vs. Verifying
  3. P vs. NP
  4. NP-Completeness
  5. Solving NP-Complete Problems Efficiently
  6. Consequences
• The Halting Problem
  1. Writing the Perfect Verifier
  2. Programs as Input
  3. halts() and breakHalts()
  4. Consequences
• Data Representation
  1. Bits and Bytes
  2. Representing Non-discrete Values
  3. Consequences

• P vs. NP
  
  1. Complexity Classes
     
     • In the Efficiency unit we showed that algorithms fall into different function families. Complexity families are the same idea, but generalized even more.
     • Specifically, we care about two main complexity classes: exponential time and polynomial time. Generally we want to write algorithms that can run in polynomial time. We call these functions 'tractable'.
     • We'll say that a function is in P if it runs in polynomial (O(n**k) for some integer k) time.
  
  
  2. Solving vs. Verifying
     
     • Usually, when we are working with a problem, we want to solve the problem by writing an algorithm that finds a solution.
     • Sometimes, we also care about verifying solutions to a problem. Given a possible solution, how much time does it take to check whether it works?
     • We'll say that a function is in NP if it can be verified in polynomial time, regardless of how long it takes to solve. NP stands for nondeterministic polynomial in this context.
     • Example: subsetSum. Given a list of n elements, is there a subset of the list where the elements sum to 0?
       
       
       # Obvious solution: findSolution has to generate every possible subset to check each one's sum. # Therefore, it runs in exponential time. Might there be a better way? def findSolution(lst, sumLst = None): if sumLst == None: sumLst = [] if len(sumLst) > 0 and sum(sumLst) == 0: return sumLst elif len(lst) == 0: return None else: result = findSolution(lst[1:], sumLst + [lst[0]]) if result == None: result = findSolution(lst[1:], sumLst) return result # checkSolution only needs to check if the sum is 0. This runs in polynomial time, # so subsetSum is in NP. def checkSolution(solution): return sum(solution) == 0
     
     
  3. P vs. NP
     
     • A lot of the time, we know that a problem is in NP (can be verified in polynomial time), but the obvious solution runs in exponential time.
     • Big Idea
       • Maybe we can prove that, if we can verify in polynomial time, we can also solve in polynomial time for all problems. In other words, maybe P = NP.
       • On the other hand, if there exists at least one problem where we can verify in polynomial time and we can prove that it cannot be solved in polynomial time, P != NP (though P will still be a subset of NP in this case).
     • P vs. NP is still unsolved, and is in fact one of the seven Millennium Prize Problems.
  
  
  4. NP-Completeness
     
     • A great number of useful problems are in NP. These include:
       
       • Solving Sudoku
       • Travelling Salesman Problem
       • Graph Coloring
       • Knapsack Problem
       • Boolean satisfiability problem
       • Scheduling
       • ...
     • For many of these problems, it's possible to transform (or reduce) problem A into problem B in polynomial time.
     • Some problems can be reduced from all other NP problems in polynomial time; these are called NP-Complete.
     • If we can find a polynomial-time solution to any NP-Complete problem, we can prove that P=NP, since that polynomial-time solution could be combined with the polynomial-time reduction to achieve still-polynomial solutions to all other NP problems.
  
  
  5. Solving NP-Complete Problems Efficiently
     
     • We don't have efficient solutions to NP-complete problems. In many cases, however, we can use heuristics to estimate a solution that is good enough.
     • Consider the problem of scheduling final exams:
     • Given a set of courses, students, rooms, and student course schedules, find the shortest possible final exam schedule that guarantees no student has two exams at the same time.
     • This problem is NP-complete, so finding the optimal solution is not currently feasible.
     • However, we can solve for solutions that are close to optimal. This means that while we might not be able to find the shortest possible exam schedule, we might find one that is close to the shortest.
     • In practice, finding a close solution is often good enough. If this interests you, you can read more about constraint satisfaction problems.
     • The ability to identify that a problem you are solving is not efficiently solvable is an important skill for a programmer and can save you lots of wasted time.
  
  
  6. Consequences
     
     • If P=NP, answering questions that are currently considered difficult could suddenly become much easier. Scheduling and other logistical questions could be almost entirely automated, and most mathematical work could be done entirely with computers. However, this would also impact cryptography, as certain types of encryption would be breakable in much more efficient time.
     • If P!=NP, life would continue on as normal. However, we will also have gained a way to formally demonstrate that certain problems cannot be solved efficiently, which could reduce the number of open questions researchers investigate.
  
  
• The Halting Problem
  
  1. Writing the Perfect Verifier
     
     • Testing is important, as we established early in the semester. However, test cases are not infalliable; we may sometimes forget to include a specific test case, which means that our code may break unexpectedly when we provide it with new input.
     • It would be great if we could write a program that could test any given program to make sure it works correctly on all possible inputs. First, though, we have to make sure that the program actually finishes running for all possible inputs.
     • The Halting Problem: can we write a program that checks an input program to make sure it doesn't run forever? In other words, can we determine whether the input program halts?
  
  
  2. Programs as Input
     
     • Before we can solve the halting problem, we have to determine how to use programs as input.
     • Programs can be represented as text; therefore, we can pass a program in as a string, then use exec to evaluate the code directly.
     
     
     import io, sys def run(programString, inputString): tmp = sys.stdin sys.stdin = io.StringIO(inputString) try: exec(programString, globals()) except Exception as e: print("Error:", e) finally: sys.stdin = tmp # First, let's just run an everyday program: p1 = ''' def fib(n): return 1 if (n < 2) else fib(n-1) + fib(n-2) N = int(input()) print([fib(n) for n in range(N)]) ''' # Run a program with expected input run(p1,'7') # --> [1, 1, 2, 3, 5, 8, 13] # Run the same program with itself as input (crashes) run(p1, p1) # --> Error: invalid literal for int() with base 10: '' # Now let's patch p1 so that it does not crash on non-int input, # so it can run with itself as input: p2 = ''' def fib(n): return 1 if (n < 2) else fib(n-1) + fib(n-2) inputLine = input() try: N = int(inputLine) except: N = len(inputLine) print([fib(n) for n in range(N)]) ''' # Program still works as expected run(p2,'7') # --> [1, 1, 2, 3, 5, 8, 13] # And now runs (at least halts) on itself as input run(p2, p2) # --> [] (why?)
  
  
  3. halts() and breakHalts()
     
     • Now that we can handle programs as input, we can write a program runsForever, which detects whether the given program runs forever on any given input.
     • First, we'll solve a sub-problem. We'll write the function halts, which takes both program and input and detects whether the program halts on that input. We can then call halts on all possible inputs to solve runsForever.
     • Actually, it turns out that it's really hard to write a program like halts. Maybe it's even impossible! We can now try to derive a proof by contradiction to see if this halts program could ever exist.
     
     
     # First: let's just ASSUME that someone somehow was super-clever and figured # out a way to write this halts() function. We can write this program, # that uses that halts() function: p4 = ''' def breakHalts(programString): inputString = programString # provide the program as input to itelf! if (halts(programString, inputString)): print('Running forever!') while True: pass else: print('Halting!') return ''' # Try running breakHalts on code that hangs: code = '''def f(tmp): while True: pass''' run(p4, code) # will halt (if halts() works correctly) # Try running haltingProblem (p4) on code that halts code = '''def f(tmp): print(1 + 2)''' run(p4, code) # will hang (if halts() works correctly)
     
     
     • Now we get to our main question: does breakHalts() halt when given itself as input?
       1. Possibility 1: breakHalts does halt when given itself. Then the if statement evaluates to True, and we immediately enter an infinite while loop. Contradiction!
       2. Possibility 2: breakHalts does not halt when given itself. Then the if statement evaluates to False, and we immediately exit the function. Contradiction!
     • This program cannot logically exist! But almost all of its components are just fine; the only exception is the existance of halts() itself. Therefore, the program halts() cannot exist.
  
  
  4. Consequences
     
     • We've proven that we can't write a function which can always determine whether the given program halts on the given input. This means that it is impossible for us to prove that a given program will always behave correctly on a given input as well.
     • We define impossible functions like the halts() function to be uncomputable; in other words, they can't be solved with a program. Many functions fall into this category!
     • While we cannot write a function for every possible function on every possible input, we can write halting functions on restricted inputs for specific functions. This lets us prove that certain functions will always behave correctly on specific kinds of input.
     • It actually makes sense that we can't always determine whether a program halts! Otherwise, we'd be able to prove crazy things...
     
     
     # Goldbach's Conjecture: every even number greater than 2 is the sum of two primes # This conjecture seems to be right, but we've never been able to prove it. def findGoldbachViolation(): # halt if/when we find an even number > 2 that is not the sum of two primes def isPrime(n): if (n < 2): return False if (n == 2): return True if (n % 2 == 0): return False for factor in range(3,round(n**0.5)+1,2): if (n % factor == 0): return False return True def goldbachWorks(even): # return true if this even is the sum of two primes, false otherwise for p in range(2, even): if (isPrime(p) and (isPrime(even-p))): return True return False even = 4 while True: if (not goldbachWorks(even)): print('Found the violation at even =', even) return False even += 2 # never halt if Goldach's conjecture is True if (halts(findGoldbachViolation, None)): print("Goldbach's Conjecture is False!") else: print("Goldbach's Conjecture is True!")
• Data Representation
  
  1. Bits and Bytes
     
     • Computers represent information using different voltage levels (low and high). This means that each piece of infomration can only have two values- 0 or 1.
     • We call a single piece of information stored by a computer this way a bit. Multiple bits can be combined to store larger pieces of information; for example, a byte is composed of eight bits, which means it can represent 2⁸ = 256 distinct values.
     • At the lowest level, bits are used to represent everything in computers. Numbers, words, pictures, videos- everything is just combinations of bits that the computer knows how to interpret!
     • We can represent any integer using a combination of bits. We can do this by converting the integer to binary (its value in base 2), which is represented entirely by 0s and 1s. In other words, we're looking for a combination of powers of 2 that, when summed together, form the number.
       • If we want to represent 35, we would say 2⁵ + 2¹ + 2⁰ = 32 + 2 + 1 = 35.
       • We can rewrite this as 1*2⁵ + 0*2⁴ + 0*2³ + 0*2² + 1*2¹ + 1*2⁰. Therefore, 35 in base 2 is 100011.
     • Now that we have a mapping from integers to bits, we can also represent strings with bits! Strings are just a series of characters, and each character can be represented by a number (its ascii value). That means we can translate a string into a series of numbers, and then translate those numbers into a series of bits.
       • If we want to represent "code", we would first map it to individual characters, "c" + "o" + "d" + "e".
       • We would then map each character to its ascii value. "c" = 99, "o" = 111, "d" = 100, "e" = 101.
       • Finally, map each of these numbers to its binary value. Mandate that each number must be eight digits long (the longest ascii value). 99 -> 01100011, 111 -> 01101111, 100 -> 01100100, 101 -> 01100101.
       • Our final string representation is 01100011011011110110010001100101.
  
  
  2. Representing Non-discrete Values
     
     • Now we know how to represent values like integers in strings in a computer. But what happens when we need to represent values that aren't discrete (finite)?
     • For example: decimal numbers, like 1/10, or 1.5112, or pi. We can't convert these to binary values, so how can we perfectly represent such values in finite space?
     • We can't! But we can approximate the value to a certain degree of precision. We'll use a similar approach to representing integers: find a sum of powers of 2, but now use negative powers to get the numbers after the decimal points. This will let us exactly represent some decimal numbers, and get fairly close to others. However, we'll always need to bound our calculations by the number of powers we're willing to compute.
       • Example: let's say that we'll only go from 2⁰ to 2^-7 (eight bits total).
       • This lets us represent 1.4375 perfectly: 1*2⁰ + 0*2^-1 + 1*2^-2 + 1*2^-3 + 1*2^-4 + 0*2^-5 + 0*2^-6 + 0*2^-7 = 1.4375, and its representation is 10111000.
       • On the other hand, we can only approximate 1/10: 0*2⁰ + 0*2^-1 + 0*2^-2 + 0*2^-3 + 1*2^-4 + 1*2^-5 + 0*2^-6 + 1*2^-7 = 0.1015625. This gives us an error: 0.0015625. But 00001101 is the closest we can get with only eight bits!
  
  
  3. Consequences
     
     • The more bits we use, the more precise the value will be. However, this will also require more space in the computer. Data representation always has a conflict between precision and space. And we haven't even gotten into the question of range yet- how do we represent decimal values that don't start with 0 or 1?
     • In practical terms, as we saw above, this can lead to incorrect calculations!
     • 1/10 was only slightly off, but this small error can propogate. This even happens in Python (which uses a much larger representation) when we add 1/10 + 1/10 + 1/10.
     • In the real world, this can have deadly consequences. For example, the Patriot Missile failure happened due to a floating point error in radar timestamps. The error was tiny, but the change in the computed location was half a kilometer! Tiny errors can cause big problems!
     • There are ways to better represent certain subsets of decimal numbers, but its important to remember that no representation can perfectly represent all numbers.