patternMinor
NP languages definition
Viewed 0 times
languagesdefinitionstackoverflow
Problem
Is it good to define a language $\mathcal{L}$ in NP as a language for which, given an element $x$, it is possible in polynomial-time to check whether $x \in \mathcal{L}$ or not?
Because I need to have an informal definition of that, in order to give just an idea of it, without using formalism.
Otherwise how could I define it roughly speaking?
Because I need to have an informal definition of that, in order to give just an idea of it, without using formalism.
Otherwise how could I define it roughly speaking?
Solution
Is it good to define a language $\mathcal{L}$ in NP as a language for
which, given an element $x$, it is possible in polynomial-time to
check whether $x \in \mathcal{L}$ or not?
No. If you could do that you could "check" that this language would be in P, because you can check (or more formally decide) all possible words for membership in polynomial time this way.
A correct formulation would be:
A language $\mathcal L$ is in NP if for every word $x$ in the language there exists a witness $w$ which is of length polynomial in the length of $x$ and given the witness and the word you
can verify language-membership in polynomial time.
Note that you only need said witness (sometimes also called certificate) need only exist for words that actually are in the language, i.e. you don't need to be able to construct them for negative instances and constructing them is allowed to take super-polynomial time.
which, given an element $x$, it is possible in polynomial-time to
check whether $x \in \mathcal{L}$ or not?
No. If you could do that you could "check" that this language would be in P, because you can check (or more formally decide) all possible words for membership in polynomial time this way.
A correct formulation would be:
A language $\mathcal L$ is in NP if for every word $x$ in the language there exists a witness $w$ which is of length polynomial in the length of $x$ and given the witness and the word you
can verify language-membership in polynomial time.
Note that you only need said witness (sometimes also called certificate) need only exist for words that actually are in the language, i.e. you don't need to be able to construct them for negative instances and constructing them is allowed to take super-polynomial time.
Context
StackExchange Computer Science Q#97184, answer score: 8
Revisions (0)
No revisions yet.