Yioop - PHP Search Engine

Practice Final Question #8.

Originally Posted By: confusedNotle

Come up with a bounded version of the REGULARTM problem from class such that this variant is now NP complete under Karp-reductions. Prove this.

We came up with a bounded version of the REGULARTM problem from class by coming up with a TM REGULARClockedTM.

Since the map  can be viewed as a reduction from REGULARTM to ATM, the map  can be viewed as a reduction from REGULARClockedTM to AClockedTM.

AClockedTM := {|M is a nondeterministic machine that accepts w in at most t steps} is Karp-complete for NP.

We first show AClockedTM is in NP. A nondeterministic algorithm to recognize this language is as follows: On input , nondeterministically guess a string v of length t^2, then verify that v codes a sequence of configurations of M of length t, the first being the start configuration of M on w, and such that the i + 1st configuration follows from the ith. If it does, M accepts w, then accept, else reject. Now suppose L is in NP. Then, it can be decided by some nondeterministic machine M in time p(n) for some polynomial p. The function w  is polynomial time computable and gives a reduction from L to AClockedTM.

Thus, REGULARClockedTM is now NP complete under Karp-reductions, assuming it accepts.

Elton Murillo
Pin Chang
Jake Askeland
Jerry Wong
Jeremy Lozano

'''Originally Posted By: confusedNotle''' Come up with a bounded version of the REGULARTM problem from class such that this variant is now NP complete under Karp-reductions. Prove this. We came up with a bounded version of the REGULARTM problem from class by coming up with a TM REGULARClockedTM. Since the map  can be viewed as a reduction from REGULARTM to ATM, the map  can be viewed as a reduction from REGULARClockedTM to AClockedTM. AClockedTM := {|M is a nondeterministic machine that accepts w in at most t steps} is Karp-complete for NP. We first show AClockedTM is in NP. A nondeterministic algorithm to recognize this language is as follows: On input , nondeterministically guess a string v of length t^2, then verify that v codes a sequence of configurations of M of length t, the first being the start configuration of M on w, and such that the i + 1st configuration follows from the ith. If it does, M accepts w, then accept, else reject. Now suppose L is in NP. Then, it can be decided by some nondeterministic machine M in time p(n) for some polynomial p. The function w  is polynomial time computable and gives a reduction from L to AClockedTM. Thus, REGULARClockedTM is now NP complete under Karp-reductions, assuming it accepts. Elton Murillo Pin Chang Jake Askeland Jerry Wong Jeremy Lozano

-- Practice Final Question #8

Originally Posted By: lambert

So how do we reduce Regular_clockedTM to A_clockedTM? Is there an algorithm or a machine that we can build to map regular_clocked to A_clocked? because the second part asks us to prove

'''Originally Posted By: lambert''' So how do we reduce Regular_clockedTM to A_clockedTM? Is there an algorithm or a machine that we can build to map regular_clocked to A_clocked? because the second part asks us to prove

-- Practice Final Question #8

Originally Posted By: confusedNotle

You can look at the following slide for the complete proof:
http://www.cs.sjsu.edu/faculty/pollett/154.1.11s/Lec27042011.html#(6)

'''Originally Posted By: confusedNotle''' You can look at the following slide for the complete proof: http://www.cs.sjsu.edu/faculty/pollett/154.1.11s/Lec27042011.html#(6)

-- Practice Final Question #8

The solution posted doesn't make sense to me.

You need to
(1) state what your bounded version of REGULAR_TM is
(2) show it is in NP.
(3) prove every language in NP can be reduced to it.

You mention REGULAR clocked tm without given any definition. As such it is impossible to determine if you have
made any progress on (2) or (3).

The solution posted doesn't make sense to me. You need to (1) state what your bounded version of REGULAR_TM is (2) show it is in NP. (3) prove every language in NP can be reduced to it. You mention REGULAR clocked tm without given any definition. As such it is impossible to determine if you have made any progress on (2) or (3).