Yioop - PHP Search Engine

Midterm2 Practice Question 4.

Originally Posted By: snigdhamokkapati

I have a doubt regarding the 4th question in practice midterm. It is given as
Explain why SATH for the H we used in the proof of Ladner's Theorem is neither in P nor in NP.

I am a little confused here. Shouldn't it be SATH is neither in P nor NP-Complete?

And also it would be great if someone can post the answer to this in simpler words.

'''Originally Posted By: snigdhamokkapati''' I have a doubt regarding the 4th question in practice midterm. It is given as Explain why SATH for the H we used in the proof of Ladner's Theorem is neither in P nor in NP. I am a little confused here. Shouldn't it be SATH is neither in P nor NP-Complete? And also it would be great if someone can post the answer to this in simpler words.

-- Midterm2 Practice Question 4

Originally Posted By: sctice

I think you're right about the question, and indeed, I answered as though it read:

Explain why SAT_H for the H we used in the proof of Ladner's Theorem is neither in P nor NP-complete.

I've updated the problem statement under the assumption that that's what the question is supposed to be, and I tried to strip out the core of the explanation and put it up at the top. I hope it's more helpful to you.

Cheers,
Shawn

'''Originally Posted By: sctice''' I think you're right about the question, and indeed, I answered as though it read: Explain why SAT_H for the H we used in the proof of Ladner's Theorem is neither in P nor NP-complete. I've updated the problem statement under the assumption that that's what the question is supposed to be, and I tried to strip out the core of the explanation and put it up at the top. I hope it's more helpful to you. Cheers, Shawn

-- Midterm2 Practice Question 4

Originally Posted By: snigdhamokkapati

Yes .. now it makes sense .. and thank you for the explanation shawn .. you made it really interesting by putting it as a conversation .. that clears the little doubts I have here and there ..

'''Originally Posted By: snigdhamokkapati''' Yes .. now it makes sense .. and thank you for the explanation shawn .. you made it really interesting by putting it as a conversation .. that clears the little doubts I have here and there ..