8
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ This article (cs.uky.edu/~lewis/cs-heuristic/text/class/p-np.html) puts some nice examples on the issue. $\endgroup$
    – Masroor
    Commented May 16, 2013 at 15:26
  • 2
    $\begingroup$ These notions are not restricted to P and NP. Go back to the chapter about computability and enumerability. And look at the formal definitions. $\endgroup$
    – Raphael
    Commented May 17, 2013 at 6:42

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ There is no "it" to find. P and NP are decision classes, so it's not a search problem, it's a yes/no problem. A potential solution to the problem might involve searching, i.e. if the problem asks "does there exist...", but technically there's no need to "find" something, just to test if a condition is true or false. $\endgroup$
    – Joey Eremondi
    Commented May 16, 2013 at 17:21
  • $\begingroup$ Ok sorry, my bad. You are totally right. $\endgroup$
    – wece
    Commented May 16, 2013 at 17:23
  • $\begingroup$ post deleted thanks for your corrections. an sorry again for my mistake. $\endgroup$
    – wece
    Commented May 16, 2013 at 23:31
  • $\begingroup$ No need to be sorry! $\endgroup$
    – Joey Eremondi
    Commented May 16, 2013 at 23:31
  • $\begingroup$ well it may have been more confusing than helpfull ... $\endgroup$
    – wece
    Commented May 16, 2013 at 23:32
1
$\begingroup$

suppose you give me a problem and you asked me a solution so let's say that you can check only polynomial amount of my proof (that is : you can run efficient computer program on my proof) when I send you my proof of the solution all what you do is to run your program and decide according to what the program output .
for example : suppose you ask me if a graph is 3-colorable , then what I have to do is to sent a 3 coloring of the graph then you check if all adjacent vertices have different colors then the coloring is legal and the program terminate with "accept"(otherwise the proof is not accepted and we terminate with "reject") .
that's called to verify "quickly".
if you can build a "efficient" "computer program"(or simply: polynomial algorithm) that say if an input(a string of length n) is in the language (or if the program output 1\"accept") this is what do mean by complexity class P.
example : suppose I give you a list of strings (lets say telephone book ) and asked you about a name that you must say if it is in the book or not . one solution is to go throw all the names and compare each name with the given name, that says you can solve it in linear time.
another example is : given a graph G=(V,E) and an edge e=(u,v) and you want to say if the edge is in the graph .

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.