Transcript ATM, Halting Problem, P vs. NP

ATM, Halting Problem, P vs. NP
Chapter 4, 5 & 7
Russel’s Paradox
• http://www.jimloy.com/logic/russell.htm
• An Index is a book that lists other books in the library
– Index of all biology text books in the library.
• Consider the index of all indices, i.e., book that lists other indices.
– It would contain itself.
– Called a self-referential index (form of recursion).
• Consider the index of all non self-referential indices.
– The book that lists all indices that are non self-referential.
– Call it the non-recursive index
1.
2.
If the non-recursive index lists itself then its recursive and
shouldn’t be in the list.
But if it doesn’t list itself, then it is non-recursive and it should be
listed as one of the non self-referential books.
ATM reduces to HALTTM
• Proof by Contradiction
– Assume we have a Turing Machine R that decides
HALTTM.
• In other words, we can design an algorithm that
determines of another algorithm (M) will halt on a
given input (w).
ATM reduces to HALTTM
• Proof by Contradiction
– Assume we have a Turing Machine R that decides
HALTTM.
– Then, use R to construct a new machine S that can
decide ATM.
– We have already proven that is NOT decidable.
– So, if we can construct a machine S that can
decide ATM based on HALTTM then we must
conclude that cannot be decidable.
ATM reduces to HALTTM
• Proof by Contradiction
– Assume we have a Turing Machine R that decides
HALTTM.
– Then, use R to construct a new machine S that can
decide ATM.
– We have already proven that ATM is NOT
decidable.
– So, if we can construct a machine S that can
decide ATM based on HALTTM then we must
conclude that cannot be decidable.
Deeply Understanding ATM
• ATM is just a set of strings where part of the string is the
encoding of a Turing Machine (M) and the other part is an
input string (w).
– The string in ATM are the ones were the input w is accepted by
the Machine M.
– The string in the complement of are the ones the input w is
rejected by the Machine M.
• A decider for ATM cannot exist because there are absurd
Turing Machines infinite loop or output nothing.
• Detecting such absurdity is impossible because you are
limited by the power of the same machine that allows for
such absurdity.
– Simulating an absurd Turing Machine with another Turing
Machine cannot “undo” it absurdity and allow it to always
produce an answer (accept or reject).
Chapter 7
Time Complexity
Big-O
Little-o
O(n2)
O(n log2n)
O(n)
Non-determinism
The Cost of Non-determinism
The Class P
Example of a problem in P
PATH is polynomial
The Class NP
Polynomial Verification
• Some problems (Hamiltonian Path) cannot be
solved in Polynomial Time (P), but…
• If we could somehow obtain a solution (ask an
oracle), the solution could be verified in Ptime.
Hamiltonian Path: Decider vs. Verifier
• There is very subtle difference:
• Hamiltonian Decider
– Input: Graph
– Output: Hamiltonian Path
• Hamiltonian Verifier
– Input: Graph, Hamiltonian Path
– Output: Accept/Reject
Hamiltonian Path Algorithm – Nondeterministic
Understand NP in English
• Problems where the solutions can be verified
in P-Time, but cannot be “discovered” in Ptime
• Problems where the solutions can be
“discovered” P-Time using a Nondeterministic Turing Machine
• Note: Every non-deterministic Turing machine
can be made deterministic by adding O(kn)
Non-determinism  O(kn)
• k is usually 2
– Given a graph with n vertices, there are 2n possible
subsets.
• 2 options for each vertex
• Either you are in the subset (1) on not (0)
• Binary state condition
– Given a list with n value, there are 2n possible
subsets
Non-determinism  O(kn)
“Non deterministically select a subset implies 2n
operations.”
• This is a loop through a Turing machine state
that has a branching non-deterministic
transition
• For each n vertex regardless of the tape
symbol
– Add (1) the vertex to the subset and continue
– Don’t add (2) the vertex and continue