P v NP

Halting Problem

• Given a program and an input, will the program halt?
  • Can a program be written to analyze whether a program will halt? (without running the inputted program)

`
String test = “
    public boolean proof_sketch(String program) {
    if (WILL_EVENTUALLY_HALT(program, program)){
        while (true){}
        return false;
    }
    else {
        return true;
    }
  }
”;
proof_sketch(test);
`

• The WILL_EVENTUALLY_HALT() function detects whether the code entered will halt
• We pass in the function given and it will contradict itself

Intractable Problems

• Solvable, but they would take too much time to be solved practically for normal sized inputs
  • Listing all subsets of a set: O(2^n)
  • Listing all permutations of a set: O(n!)

P is for Polynomial

• Runtimes with constant exponents
  • n^2, nlgn, etc
• Shortest Path problem
  • Solvable with Dijkstras in polynomial time
• Longest path
  • lol nah bro. That's hard.
• But we can solve it...so what is it

P v NP

• P
  • The set of all problems that can be solved by deterministic algorithms in polynomial time
• NP
  • The set of all problems that can be solve by NON-deterministic algorithms in polynomial time
  • The N stands for non-deterministic
  • Solutions from non-deterministic algorithms can be solved in polynomial time
• non-deterministic? Uh...kinda just magic or whatever
  • Runs as fast as choosing the right step, O(1)

Example: Hamiltonian Cycle

• A hamiltonian cycle is a cycle through a graph that visits every vertex
• Can this be solved?
  • Yeah, brute force. Just check every possible cycle.
• But this would take v!
• Can we verify the result in polynomial time?
• Yes! We just go through the cycle and check every vertex. Done in v time

P = NP?

• We know either P and NP are the same, or that P is a subset of NP.
• Neither has been proven or disproven
• We can prove P != Np by showing an NP problem is intractable
• We can prove P = NP by finding a polynomial solution to a known NP problem
• If P = NP:
  • Cryptography would break
    • Efficient algorithms would exist to break all they cryptography stuff. It bad.
  • But a lot of other stuff would benefit, like predicting protein structures, making automated maths proofs, and there would exist a polynomial solution to stuff like traveling salesman
• If P != NP:
  • Nothing.
  • We assume this to be the case

NP-Complete

• These are the hardest problems in NP
  • They are equally "hard"
• Prove NP-Completeness
  • We show that the solution to our problem could be used to solve another NP-Complete problem