Ch 5 : Reducibilty Flashcards
What is the primary method for proving that problems are computationally unsolvable?
Reducibility
What is the definition of a reduction?
converting one problem to another problem in such a away that a solution to the second problem can be used to solve the first problem.
If A reduces to B, we can use a solution to B to solve A.
(** nothing about solving a or b on their own, but only about the solvability of A with regard to B)
How do we use reducibility?
When A is reducible to B, solving A CANNOT be harder than solving B, because solving B gives a solution to solving A.
If A is reducible to B, and B is decidable, A is also decidable.
Also if A is undecidable and A reduces to B, B is undecidable. (**THIS IS THE KEY TO PROVING PROBLEMS UNDECIDABLE)
How do we show a problem is undecidable?
We show that some other problem we already know to be undecidable reduces to it.
What is the computation history for a machine?
the sequence of configurations that the machine goes through as it processes the input.
What is computation history a good tool for?
Proving A.TM is reducible to certain languages. Often when the problem to be shown inclues testing for the existence of something.
How many computation histories do different types of machines have?
A machine that doesn’t halt on w has no accepting or rejecting computation history for w.
deterministic machines have exactly 1 history.
non-deterministic machines have multiple histories.
What are three parts of a computation history for M.
C1 is the start state. Cl is the accept(or reject state) and Ci+1 legally follows from Ci.
What is the definition of a linear bounded automata (LBA)?
a restricted Turing machine where the head isn’t permitted to move off the portion of the tape containing the input. IF it tries to move either way off the input, the head stays where it is.
Describe the memory of an LBA?
Its memory is obviously limited. it can only solve problems requiring memory less than what can fit in the size of the input tape. with a tape alphabet larger than the input alphabet, the available input can be increased up to a constant factor.
For an input of length n, the amount of memory avail is linear in n, thus the name of the model.
Why is A.LBA being decidable significant?
Because its the same as the undecidable problem A.TM but the only difference is the machine is restricted to being an LBA. We can see that linearly bounded the automata makes the acceptance problem decidable.
What is another name for mapping reducibility? Why does this name make sense?
Many to one reducibility….
What is the definition of mapping reducibility?
a computable function exists that converts instances of problem A to instances of problem B.
Any instance of A can then be solved by first using the reduction to convert it to an instance of B, then applying the solver for B.
What does a Turing machine do for computable functions?
If the TM, M starts with w on its tape, its halts with only f(w) on its tape.
What is the definition of a mapping reduction from A to B?
A E* where for every w, w E a IFF f(w) E B.
