-- HW-3 Q-3
Originally Posted By: jnewth
The first part of this problem is straightforward. We've shown problems to be in NP before, and this is only a slight modification on that.
The difficulty is reducing some other NPA language L to SATA. The Cook-Levin reduction shows us how to do this for an NP language L to SAT but I have a few questions:
The Cook-Levin reduction uses a 2-tape oblivious machine, but the concept of an oracle has been described in the book as having an additional tape called the oracle tape, where, when the machine M that decides the language L enters Qquery, reads the oracle tape and then transitions to Qyes or Qno.
Can we simply repeat the Cook-Levin reduction with this additional tape and a consideration of the states Qquery, Qyes and Qno? This tape is not oblivious. What information do we need to track for that? I'm probably missing something important but it seems like if we just modify our function F that computes Zi from the tuple {Zi-1, Zprev(i), Yinputpos(i)} to account for the Qquery transitions, we're okay.
'''Originally Posted By: jnewth'''
The first part of this problem is straightforward. We've shown problems to be in NP before, and this is only a slight modification on that. <br><br>The difficulty is reducing some other NPA language L to SATA. The Cook-Levin reduction shows us how to do this for an NP language L to SAT but I have a few questions:<br><br>The Cook-Levin reduction uses a 2-tape oblivious machine, but the concept of an oracle has been described in the book as having an additional tape called the oracle tape, where, when the machine M that decides the language L enters Qquery, reads the oracle tape and then transitions to Qyes or Qno. <br><br>Can we simply repeat the Cook-Levin reduction with this additional tape and a consideration of the states Qquery, Qyes and Qno? This tape is not oblivious. What information do we need to track for that? I'm probably missing something important but it seems like if we just modify our function F that computes Zi from the tuple {Zi-1, Zprev(i), Yinputpos(i)} to account for the Qquery transitions, we're okay.