Re: Why isn't NP simply "not polynomial"?

In article <002f4449-a1a8-4c83-9056-a550d96451de@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Digital Puer <digital_puer@xxxxxxxxxxx> wrote:
Why do we have to bring in non-determinism at all?

Why can't NP be defined as the class of decision problems
for which the best (known) solution is a *deterministic*
superpolynomial solution algorithm?

It is certainly possible to define a class Not-P (I'll use a different
notation from "NP" so as to avoid confusion with standard terminology)
to be the class of all decision problems that are *not* solvable in
polynomial time. However, the definition of Not-P does not give us any
more insight into complexity theory than P itself does. It's trivially
equivalent to P, so studying Not-P is really the same as studying P.

Now, you put in the parenthetical word "known" in your suggested
definition, whereas I did not. Inserting that word changes everything.
Suppose we define Not-Known-P to be the class of decision problems for
there is no *known* polynomial time algorithm. This would indeed be a
concept that is different from P in an essential way. However, it has
the awkward property that it depends on the current state of human
knowledge. A particular problem might be in Not-Known-P today and it
might be in P tomorrow. It is very useful to have mathematical theorems
whose validity does not change with time, so concepts like Not-Known-P
are typically excluded from formal mathematical discourse.

While the above paragraphs explain why you don't find the concepts Not-P
and Not-Known-P in your textbooks, they don't explain why you *do* find
the concept of NP in your textbooks. You should not expect to find any
explanation of the form, "It is totally obvious that we ought to consider
the class of non-deterministically polynomial-time solvable algorithms
because..." followed by some reason that makes it totally obvious. The
class NP is *not* obvious. Cook, Karp, and others get a lot of credit
for their insight that NP is an important class of problems to consider.

Although it is not obvious *a priori* why one should consider NP, it is
possible to see, with the benefit of hindsight and many years of experience,
that it is indeed an important class of problems to consider. As someone
else suggested, perhaps the best way to think about NP is not in terms of
the usual formal definition of non-determinism, but as the class of
problems with the property that you can *check* a solution that is given
to you in polynomial time. That is, you may or may not be able to *find*
a solution in polynomial time, but if someone hands you a solution, you
can quickly check that the solution is correct. A vast number of real-world
problems have this property; in fact, I would venture to say that *most*
problems that crop up in practice are in NP. On the other hand, it is easy
to contrive problems that are definitely *not* in NP. Putting these two
facts together (1. most real-world problems are in NP; 2. not every problem
is in NP) suggests that it would be fruitful to define precisely what NP
is and study it.

For instance, the subset-sum problem is pretty
obvious to me: the running time to solve it has to
run in O(2^N) time, which is super-polynomial.
Since it is "not polynomial" it can't be in P and
must be in NP.

Subset-sum is in Not-Known-P, yes. However, even this fact is not obvious;
you need to check the published literature to verify that nobody has a
clever polynomial time algorithm for it. All that you have shown is that
Subset-sum is in Not-Known-to-Digital-Puer-P.

Even after a literature search confirms that subset-sum is in Not-Known-P,
it remains an open question whether subset-sum is in Not-P. This is not
known; subset-sum is currently in Not-Known-Not-P as well as in Not-Known-P.

Subset-sum is indeed in NP, according to the standard definition of NP, but
nothing you or I have said so far establishes this fact. We must establish
that a solution to the subset-sum problem can be verified in polynomial
time. Lack of ability to find a polynomial time algorithm has nothing to do
with membership in NP.

Why kind of problems fall into NP but are not in P
and are not in NPC, assuming P != NP?

Look up Ladner's theorem. There aren't any really "natural" examples of
such problems, but you can contrive them by restricting NP-complete problems
to certain subclasses of instances. Papadimitriou's book "Computational
Complexity" has some examples.

For these problems in NP, am I correct in assuming that other
problems in NP cannot be reduced to these problems?

Some other problems in NP can be, but not all of them. By definition, if
*every* other problem in NP can be reduced to a particular problem, then
that problem is NP-complete.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • Re: Distance normalized TSP algorithm
    ... have not seen it applied to TSP, but I suspect that is mainly because it ... more challenging than that, but perhaps a bit less challenging than ... finding a polynomial time algorithm for an NP-complete problem. ...
    (comp.lang.java.programmer)
  • Re: Aspiring highest-order programmer
    ... >> active knowledge into dead secrets in such a way that one can never, ... the moment someone comes up with a polynomial time ... > polynomial time algorithm to solve the problem which makes the problem ... Doesn't this fail to answer the question as to the practicality of the ...
    (comp.programming)
  • hi guys...need insight into this interesting algorithm..Repost
    ... I need to devise a polynomial time algorithm which given an integer ... returns a spanning tree with m number of 'A' labelled edges and ...
    (sci.math)
  • Interesting algorithm...need insights..
    ... I need to devise a polynomial time algorithm which given an integer ... returns a spanning tree with m number of 'A' labelled edges and ...
    (sci.logic)
  • Re: New integer multiplication algorithm
    ... >) Willem wrote: ... see below for why decision problems can't be NP ... > You need the non-decision solution to check in P time, ... polynomial time, then you can generally solve the corresponding ...
    (sci.math)