[Solved]: Please explain "decidability" and "verifiability"

Problem Detail: 

I am trying to (intuitively) understand the two terms "decidability" and "verifiability".

I have done a reasonable amount of searching and going through the various texts I can put my hands on. However, their intuitive understanding seems to escape me, specially for the second one.

Out of the many definitions found, the following one found in this page, clearly explained decidability to me.

A language is called decidable if there exists a method - any method at all - to determine whether a given word belongs to that language or not.

However, I fail to find a parallel definition for verifiability.

In the Theory of Computation book by Sipser, we find,

P = the class of languages for which membership can be decided quickly.

NP = the class of languages for which membership can be verified quickly.

In light of the above, I want to understand verifiability.

Please provide as many examples as you can, at one moment, I try catch the meaning, in the next one, I get confused again.

Asked By : Masroor

Answered By : jmite

The key to understand here is that P and NP are classes of decision problems. That means that all of them have yes/no answers.

So when we say a problem like 3-SAT is NP-Complete, it means that given an instance of 3-SAT (aka a word potentially in the language), there is no known efficient way to test if the word is or is not in the language.

To say something is in NP means that there exists some sort of "proof" for each string in the language, which is polynomial in the length of the input.

For example, in 3-SAT, we're asking, does there exist an assignment of True/False to a set of variables in a boolean formula, such that the formula comes out to be true. The word we're testing is the boolean formula. There's no known way to find if there is a single solution that makes the whole formula true. But, if we have a set of true/false values for the variables, it's very easy to check (in polynomial time) if it causes the formula to evaluate to true.

The key point here is that the word we're testing is NOT the true/false values for each variable. The word we're testing is the formula containing the variables, and the language is the set of all boolean formulas which evaluate to true.

We don't know how to efficiently test if the word (formula) is in the language (can evaluate to true), but given a set of true/false assignments, we can verify if it evaluates to true i.e. it is a "proof" that the word (formula) is in the language. Thus the problem is in NP, but not known to be in P.

NP is actually the class of non-deterministic polynomial solvable decision problems. This is because, in a non-deterministic turing machine, we have "decision" points where we can take one of multiple actions, and our polynomial certifier is basically just telling is which decision to take at each decision point.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12068