0
$\begingroup$

I was reading the definitions of p vs np in [this post] (What is the definition of P, NP, NP-complete and NP-hard?) and I was wondering about how to classify the example decision problem where you return 1 if a natural number is even and 0 otherwise. I think this would be P complexity, but my TA said that there are infinite even numbers so it should not be P. I think there would be a way using modulo or something to solve this problem more efficiently, but I am honestly confused about P and NP in general. Note that this is not a homework question, I am just trying to wrap my head around complexity before finals.

$\endgroup$
0
$\begingroup$

The problem of deciding if a number is even is in $\mathsf{P}$, since you can design a deterministic polynomial-time algorithm for it. The exact algorithm depends on how you encode the number. If it is in unary you can just count the number of bits modulo 2, if it is in binary you can just check that the last bit is a 0.

Since this problem is in $\mathsf{P}$, it is also in $\mathsf{NP}$ (recall that $P \subseteq \mathsf{NP}$). We don't know whether the problem is $\mathsf{NP}$-complete. If that's the case, then this would imply $\mathsf{P}=\mathsf{NP}$, which is a major open problem.

The claim "there are infinite even numbers so it should not be in $\mathsf{P}$" does not make any sense. All finite languages are decidable in polynomial time but the converse is not necessarily true. The fact that there are infinitely many even numbers does not tell you anything about whether your problem belongs to $\mathsf{P}$ or not.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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