Yioop - PHP Search Engine

HW-3 Q-3.

Originally Posted By: Nishant

Q-3- "Imagine that we expand the definition of CNF to include clauses of the form A(x1,...,xn) for some language A. This clause is true if under a variable assignment the string represented by x1...xn is in the language A. Let SAT^A denote the problem of determining is a set of CNF clauses expanded with A clauses is satisfiable. Prove this problem is NP^A-complete. Show there exists an A such that SAT^A is not in P^A."?

For first part of the question, we have to prove that SAT is NP-Complete. We will require reduction for that. So, how you guys are approaching on that and in fact even what could be the certificate to prove it that it belongs to class of NP? Somehow, I'm not able to get any idea.

Also, it would be great if someone could please explain the second part.

-Nishant

'''Originally Posted By: Nishant''' Q-3- "Imagine that we expand the definition of CNF to include clauses of the form A(x1,...,xn) for some language A. This clause is true if under a variable assignment the string represented by x1...xn is in the language A. Let SAT^A denote the problem of determining is a set of CNF clauses expanded with A clauses is satisfiable. Prove this problem is NP^A-complete. Show there exists an A such that SAT^A is not in P^A."? For first part of the question, we have to prove that SAT is NP-Complete. We will require reduction for that. So, how you guys are approaching on that and in fact even what could be the certificate to prove it that it belongs to class of NP? Somehow, I'm not able to get any idea. Also, it would be great if someone could please explain the second part. -Nishant

-- HW-3 Q-3

A witness will just be a satisfying assignment. You need to show the problem is in NP^A not NP. NP^A can be defined either with an oracle NDTM or as languages
of the form
(exists y in \{0,1\}^{p(|x|)})(M^A(x,y) = 1)
where M is a deterministic p-time oracle turing machine using set A. To show it is NP complete modify the Cook Levin reduction.

A witness will just be a satisfying assignment. You need to show the problem is in NP^A not NP. NP^A can be defined either with an oracle NDTM or as languages of the form (exists y in \{0,1\}^{p(|x|)})(M^A(x,y) = 1) where M is a deterministic p-time oracle turing machine using set A. To show it is NP complete modify the Cook Levin reduction.

-- 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. 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.

-- HW-3 Q-3

For the purposes of the HW it wouldn't matter if it was oblivious or not. But modifying the Cook-Levin construction to include the oracle tape and fixing the oracle to some specific A should yield an oblivious
computation.

For the purposes of the HW it wouldn't matter if it was oblivious or not. But modifying the Cook-Levin construction to include the oracle tape and fixing the oracle to some specific A should yield an oblivious computation.