2
$\begingroup$

(I have read a lot of online articles, including on MO, SO, etc. but my question stays)


We have the following definitions: P are all deciding problems that have a polynomial algorithm

So as I understand: For $Y \subset X$ and some $x \in X$ we can say in polynomial time if $x \in Y$ or not.


Next definition:

A deciding problem $A=(X,Y)$ is in $NP$ if there is a polynomial $p$ and a deciding problem $B=(X',Y')\in P$ so that the following holds:

$X' = \{x\#c \,\,|\,\ x\in X, \, c\in \{0,1\}^{\lfloor p(\text{size}(x) \rfloor}\}$ and

$Y = \{y \in X \,\,|\,\,\exists c\in\{0,1\}^{\lfloor p(\text{size}(x) \rfloor}\,:\,y\#c \in Y'\}$


So I understand this definition the following way:

Given some $x\in X$ we want to know if $x \in Y$. In case we have a certificate $c\in\{0,1\}^{\lfloor p(\text{size}(x) \rfloor}$ appended to $x$ we can see in polynomial time if $x \in Y$, since $B\in P$.

First problem: I don't see the purpose of such a certificate. Like what would be such a certificate in praxis? Don't we just get $x$ alone instead of $x\#c$ in praxis?

Second problem: Since $x$ is non-infinite, so is $\lfloor p(\text{size}(x) \rfloor$. Therefore, we could just iterate over all $2^{\lfloor p(\text{size}(x) \rfloor}$ certificates, append them each time to $x$ and check in polynomial time if $x\in Y$. Final $O$ would be still polynomial time. So wouldn't that mean $P = NP$?

I guess I don't really see the difference between $P$ and $NP$ here.

$\endgroup$
5
  • $\begingroup$ "So as I understand: For $Y\subset X$ and some $x\in X$ we can say in polynomial time if $y\in Y$ or not." Possible typo, should it be $x \in Y$ in the last inline math environment? $\endgroup$
    – NerdOnTour
    Commented Jan 11, 2022 at 9:28
  • $\begingroup$ Yes, a typo, thx $\endgroup$ Commented Jan 11, 2022 at 9:30
  • 1
    $\begingroup$ Iterating over all certificates is certainly not polynomial on the size of x. $\endgroup$
    – Quimey
    Commented Jan 11, 2022 at 9:41
  • $\begingroup$ what is the meaning of #? $\endgroup$
    – miracle173
    Commented Jan 11, 2022 at 10:09
  • $\begingroup$ # is just a reserved divider placeholder. So just anything that is not in X and not in {0,1} $\endgroup$ Commented Jan 11, 2022 at 10:13

1 Answer 1

5
$\begingroup$

The intuition behind P is "problems which can be solved in polynomial time," and the intuition behind NP is "problems whose solutions can be checked in polynomial time." I'll try to explain how the definition of NP relates to this intuition, which should answer your first question.

When we talk about problems / languages being in NP, these problems are all decision problems: "given an input $x$, decide whether $x\in Y$." The definition of a decision problem doesn't tell us how to interpret "a solution to the problem" -- decision problems only have answers, nothing more.

So, to interpret the meaning of "solution," we add certificates. If $x\in Y$, a certificate should serve to explain why. For an example, take the satisfiability problem. If $X$ is the set of all boolean formulas, and $\text{SAT}\subset X$ is the set of all satisfiable boolean formulas, deciding whether $x\in X$ is in $\text{SAT}$ is not known to be in $P$. It's not obvious how to determine whether a formula has a satisfying assignment without checking every assignment, which can't be done in polynomial time. (I'm sure better algorithms for practical purposes are known, but none run in time polynomial in $\operatorname{size}(x)$.) However, if you know $x\in Y$, there's an easy way to convince me: tell me the satisfying assignment. To this end, we can let our certificate $c$ represent the satisfying assignment. Formally, we define $$\text{SAT}'=\big\{x\#c: x\in X\text{ and }c\text{ is a satisfying assignment of }x\big\}.$$ The satisfying assignment represents the "solution" to the problem. It may be hard to find a satisfying assignment, but it's easy to verify that one works, thereby verifying that $x$ is satisfiable.

Another, more concrete answer, comes from primality testing. (This is slightly less attractive from a theoretical point of view, since primality testing is in $P$, but it's good for explanatory purposes.) Let $X$ denote the set of positive integers, and let $Y\subset X$ be the set of composite integers. How do you convince me that an integer is composite? Well, tell me a proper factor. To this end, let $X'=X\#X$, and define $$Y'=\big\{x\#c: x,c\in X,\ c\text{ divides }x,\text{ and }1<c<x\big\}.$$ It's easy to decide membership in $Y'$: just check if $1<c<x$ and $c\mid x$. So, $Y'\in P$. If there exists some $c$ with $x\#c\in Y'$, then $x$ has a proper factor, and so $x\in Y$. This use of a factor as a certificate demonstrates that $Y$ is in NP.

A certificate won't make it any easier to solve a problem known to be in NP but not in P. However, it may occasionally be of practical importance. Say you want to know whether a positive integer is prime or composite, but you don't have enough computational power to determine the answer, and you want to know for sure. I have a lot of computational power, so I can determine the answer, but you don't trust me to do my computations correctly. If you send me the number, and I tell you it's composite, you might not believe me. But, if I tell you one of its factors, you'll be able to verify quickly and easily that it's composite. In this sense, the certificate allows you to quickly confirm the answer to the decision problem, even though solving the problem was hard.

A certificate also has theoretical importance. The name "NP" is a shortening of "non-deterministic polynomial time," which comes from non-deterministic Turing machines. These machines are a model of computation which may have multiple different "options" at each step of computation, whereas a normal Turing machine has a fixed action determined entirely by its state. Non-deterministic Turing machines don't represent how computers work in the real world, but these devices are very useful in complexity theory. To show how this relates to the certificate definition of NP, one can use the certificate to indicate which of the different options the non-deterministic machine should take, thereby turning its computation deterministic.


For your second question: You've given an algorithm to decide a language which is NP; however, this algorithm involves iterating over all strings $c$ of length $p(\operatorname{size}(x))$. This takes $2^{p(\operatorname{size}(x))}$ time, times however long it takes to check if $y\#c$ is in $Y'$. So, this algorithm isn't polynomial in the size of $x$. It does, however, show that $\text{NP}\subset \text{EXPTIME}$, where EXPTIME is the class of problem which can be solved in $2^{\operatorname{size}(x)^{O(1)}}$ time. This may not seem like a useful class, but it does have some fun complexity-theoretic applications.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .