I have this confusion related to the definition of NP problems. According to wikipedia
Intuitively, NP is the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs of the fact that the answer is indeed "yes". More precisely, these proofs have to be verifiable in polynomial time by a deterministic Turing machine. In an equivalent formal definition, NP is the set of decision problems where the "yes"-instances can be accepted in polynomial time by a non-deterministic Turing machine.
However, as far as I know NP is the set of problems which cannot be solved in polynomial time, but given a solution it can be verified in polynomial time. Now from the definition of wikipedia, I think the part where it says that they have verifiable proofs means the part that the solution can be verified in polynomial time. But I didn't get the first part where it says NP is the set of decision problems where the "yes"-instances can be accepted in polynomial time by a non-deterministic Turing machine. (Does this mean that the problem cannot be solved in polynomial time, even if it could it is by non deterministic turing machine rather than the deterministic one?).
Further I was referring to a book where it says
The input to a computational problem will be encoded as a finite binary string s. We denote the length of a string s by |s|. We will identify a decision problem X with the set of strings on which the answer is “yes.” An algorithm A for a decision problem receives an input string s and returns the value “yes” or “no”—we will denote this returned value by A(s). We say that A solves the problem X if for all strings s, we have A(s)=yesif and only if s∈X.
Now, how should we formalize the idea that a solution to a problem can be checked efficiently, independently of whether it can be solved efficiently? A “checking algorithm” for a problem X has a different structure from an algorithm that actually seeks to solve the problem; in order to “check” a solution, we need the input string s, as well as a separate “certificate” string t that contains the evidence that s is a “yes” instance of X.
The above definition from the book are hard to grasp. Can any provide some intuition?