14
$\begingroup$

[I'm not familiar with the terminology, so when I write P (resp. NP) set, I mean a subset of the integers whose membership function is a decision problem in P (resp. NP).]

Is it correct to say that a set is NP if and only if it is the image of a P set under a polynomial time function?

This seems fairly clear to me: the P set acts as the collection of verification certificates for the elements of the NP set. I'm not particularly familiar with the field though, so I wanted to check.

$\endgroup$

2 Answers 2

17
$\begingroup$

No. In particular, the images of sets in $P$ under polynomial time reductions contain many more sets than $NP$. Below I show that the halting problem is among them.

Let {$M_i$} be a list of all Turing machines. Let $f$ be a mapping from {$M_i$} $\times$ {0,1}* $\times$ {0,1}* to {$M_i$} $\times$ {0,1}* , such that

  • If $H \in~$ {0,1}* is a valid computation history that witnesses $M_i$ on $x$ halt, then $f(M_i,x,H) = (M_i,x)$. More precisely, a configuration of $M$ on $x$ is a bit string encoding the entire status of the computation at some step of $M$ on $x$: it encodes the currrent head position, the current non-blank tape contents (finite), and the current state of $M$. $H$ encodes a chronological list of every configuration of $M$ on $x$, starting from its initial configuration to its halting configuration. ($H$ could be very, very long, but it is finite, provided that $M$ halts on $x$.)

  • Otherwise, $f(M_i,x,H) = (M,0)$ where $M$ is a fixed Turing machine that halts on input $0$. We can hard-code such an $M$ into a polynomial time computable function, as it is of constant length.

Observe that $f$ is polynomial time computable! If $H$ is actually valid, then we have all the information we need to determine if $M_i(x)$ halts: the length of $H$ is at least the number of steps needed for $M_i(x)$ to halt. If $H$ isn't valid, then we can determine this by finding two adjacent configurations on the list such that the "next" configuration doesn't follow from the "previous" configuration. Each of these have length at most $|H|$ and checking the property amounts to checking a constant number of bits in each configuration: since $M_i$ is a Turing machine, at most a constant number of bits of the tape (and its current state) are manipulated in every step.

However, it is clear that the image of this polynomial time mapping is precisely the halting problem: the list of all pairs $(M_i,x)$ such that $M_i$ halts on $x$.

The gap in Joel's proof in the converse direction: the problem is that $a$ may be much much smaller in length than $b$.

$\endgroup$
5
  • $\begingroup$ You are right. I'll edit my answer. $\endgroup$ Aug 7, 2010 at 16:12
  • 2
    $\begingroup$ For completeness, I should also add that the set of valid triples $(M_i,x,H)$ (such that $H$ is a valid history of $M_i$ halting on $x$) is itself in P. This should be evident from the answer above, but should be emphasized since the question was whether we could take a P-set and transform it with a P-time function to get NP. $\endgroup$ Aug 7, 2010 at 16:17
  • 3
    $\begingroup$ The same idea shows that the sets that are the polytime functional images of P sets are precisely the computably enumerable sets. Any such image set is clearly c.e., and to realize a given c.e. set $A$, map the computation history showing $a\in A$ to the element $a$. $\endgroup$ Aug 7, 2010 at 16:59
  • $\begingroup$ Is Joel's neat characterization of c.e. sets as polytime functional images of P sets something that has been stated before? What I find weird is that P does not seem to be special in this; as far as I can tell, the argument works for any resource-bounded class C together with functions in C. I'm probably making an elementary error here -- if so, a correction would be appreciated. $\endgroup$ Aug 7, 2010 at 17:45
  • $\begingroup$ I'm sure it's known. But you are right in that the class $P$ is not alone. One can also verify a computation history in, e.g., $LOGSPACE$. Note that to determine if the next configuration follows from the current one, we must check: the two configurations have comparable lengths, the head positions are within one cell of each other, and some $O(1)$ bits in the next configuration "match up" with some $O(1)$ bits in the previous configuration. These conditions can be checked in $LOGSPACE$ using counters. However, it doesn't generalize to every class: e.g., finite automata are not sufficient. $\endgroup$ Aug 7, 2010 at 18:13
7
$\begingroup$

Every NP set is realized that way. And the characterization is correct in both directions if you add the stipulation that $f(b)$ and $b$ are polynomially related in size.

First, every NP set is a polytime image of a set in P. If a set $A$ is in NP, then there is a $P$-time decidable set $B$ of pairs (a,b) such that $a\in A$ if and only if there is $b$ such that $(a,b)\in B$. (And where the size of $b$ is polynomially restricted by the size of $a$ for all pairs in $B$.) Let $f$ be the function mapping (a,b) to a. Thus, $A$ is the image of $B$ under $f$, as desired.

Conversely, any P-time computable image of a P-time decidable set is in NP, since if $A$ is the image of $B$ under $f$, then $a\in A$ is witnessed by some $b$ such that $f(b)=a$.

Conversely, if $A$ is the image of an NP set $B$ by a function $f$ for which $f(b)$ and $b$ are polynomially related in size, then $a\in A$ is witnessed by $b$ such that $f(b)=a$.

Ryan's answer shows that an additional assumption on $f$ is required.

$\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.