* yaoziyuan@gmail.com
> Sorry. I should ask:
>
> Is this problem in NP but no in P?

Can you rephrase the problem into a decision problem?

--
Jon Haugsand
Dept. of Informatics, Univ. of Oslo, Norway, mailto:jonhaug@ifi.uio.no
http://www.ifi.uio.no/~jonhaug/, Phone: +47 22 85 24 92

From:	Rick Decker
Subject:	Re: To generate all permutations of length N
Date:	Fri, 21 Jan 2005 10:15:43 -0500

yaoziyuan@gmail.com wrote:
> Problem: To generate all permutations of length N.
> Is this problem in P but not NP?
>
First, when we talk about the classes P and NP, we generally
restrict the term "problem" to mean a decision problem,
i.e., a problem with a yes/no answer. A simple example
would be PRIME: Given a positive integer n, is n a prime?
With this in mind, your task isn't one we would usually
categorize as a "problem" in the sense we mean.

Second, if you mean "can we generate all permutations
on a set of N objects in time polynomial in the length
of the number N," then the answer is obviously no, since
it would take at least N! steps to list all the permutations.

Finally, every problem in P is also in NP, so there
are no problems in P but not in NP.

I suggest you reread the definitions of P and NP until
you understand what they're about.

Regards,

Rick

From:	Jean-Marc Bourguet
Subject:	Re: To generate all permutations of length N
Date:	21 Jan 2005 16:23:28 +0100

Rick Decker writes:

> yaoziyuan@gmail.com wrote:
> > Problem: To generate all permutations of length N.
> > Is this problem in P but not NP?
> >
> First, when we talk about the classes P and NP, we generally
> restrict the term "problem" to mean a decision problem,
> i.e., a problem with a yes/no answer. A simple example
> would be PRIME: Given a positive integer n, is n a prime?
> With this in mind, your task isn't one we would usually
> categorize as a "problem" in the sense we mean.

It is quite common to use these classes for the optimisation problem
associated to a decision one (for your example: finding the smallest
prime integer). Obviously, it is possible that a decision problem
doesn't have an associated optimisation one or that an optimisation
problem isn't associated to a decision one (and so speaking of the the
class P/NP is not meaningfull for it).

Yours

--
Jean-Marc

From:	Rick Decker
Subject:	Re: To generate all permutations of length N
Date:	Fri, 21 Jan 2005 22:56:47 -0500

Jean-Marc Bourguet wrote:
> Rick Decker writes:
>
>
>>yaoziyuan@gmail.com wrote:
>>
>>>Problem: To generate all permutations of length N.
>>>Is this problem in P but not NP?
>>>
>>
>>First, when we talk about the classes P and NP, we generally
>>restrict the term "problem" to mean a decision problem,
>>i.e., a problem with a yes/no answer. A simple example
>>would be PRIME: Given a positive integer n, is n a prime?
>>With this in mind, your task isn't one we would usually
>>categorize as a "problem" in the sense we mean.
>
>
> It is quite common to use these classes for the optimisation problem
> associated to a decision one (for your example: finding the smallest
> prime integer). Obviously, it is possible that a decision problem
> doesn't have an associated optimisation one or that an optimisation
> problem isn't associated to a decision one (and so speaking of the the
> class P/NP is not meaningfull for it).
>
Certainement, but I judged that going into more detail
would increase the OP's confusion, rather than reduce it.

Regards,

Rick

From:	Yao Ziyuan
Subject:	Re: To generate all permutations of length N
Date:	Sat, 22 Jan 2005 00:13:16 +0800

Rick Decker wrote:

>
>
> yaoziyuan@gmail.com wrote:
>
>> Problem: To generate all permutations of length N.
>> Is this problem in P but not NP?
>>
> First, when we talk about the classes P and NP, we generally
> restrict the term "problem" to mean a decision problem,
> i.e., a problem with a yes/no answer. A simple example
> would be PRIME: Given a positive integer n, is n a prime?
> With this in mind, your task isn't one we would usually
> categorize as a "problem" in the sense we mean.
>
> Second, if you mean "can we generate all permutations
> on a set of N objects in time polynomial in the length
> of the number N," then the answer is obviously no, since
> it would take at least N! steps to list all the permutations.
>
> Finally, every problem in P is also in NP, so there
> are no problems in P but not in NP.
>
> I suggest you reread the definitions of P and NP until
> you understand what they're about.
>
>
> Regards,
>
> Rick
>

I'm so guilty to ask you theory masters for explaining basic concepts...

Guilty Cat

From:	tchow at lsa.umich.edu
Subject:	Re: To generate all permutations of length N
Date:	21 Jan 2005 17:00:34 GMT

In article <1106318695.544498.39850@z14g2000cwz.googlegroups.com>,
wrote:
>Problem: To generate all permutations of length N.
>Is this problem in P but not NP?

If you actually want to generate *all* permutations, then it will take
N! time just to print out the answer, so the problem cannot be in P.

As others have pointed out, NP is a class of decision problems, and
it's not clear that there is a decision problem naturally associated
with your problem, so it's not clear what it would mean for the problem
to be in NP.
--
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

From:
Subject:	Re: To generate all permutations of length N
Date:	Fri, 21 Jan 2005 18:07:00 +0000 (UTC)

In article <41f13532$0$576$b45e6eb0@senator-bedfellow.mit.edu>,
tchow@lsa.umich.edu writes:
>In article <1106318695.544498.39850@z14g2000cwz.googlegroups.com>,
> wrote:
>>Problem: To generate all permutations of length N.
>>Is this problem in P but not NP?
>
>If you actually want to generate *all* permutations, then it will take
>N! time just to print out the answer, so the problem cannot be in P.
>
>As others have pointed out, NP is a class of decision problems, and
>it's not clear that there is a decision problem naturally associated
>with your problem, so it's not clear what it would mean for the problem
>to be in NP.

A possible decision problem might be:

Given N, a permutation p of [1,...,N] and an integer m with 1 <= m <= N!,
is p permutation number m in the list of all permutations listed in
lexicographical order?

This is the decision problem associated with the more usual problems of
finding the number of permutation p in the list, or finding permutation
number m in the list. I think these are both moderately easy polynomial-time
calculations.

Derek Holt.

From:	tchow at lsa.umich.edu
Subject:	Re: To generate all permutations of length N
Date:	21 Jan 2005 20:06:24 GMT

In article ,
wrote:
>This is the decision problem associated with the more usual problems of
>finding the number of permutation p in the list, or finding permutation
>number m in the list. I think these are both moderately easy polynomial-time
>calculations.

Yes, that's right. For example, to find the index of

37185426

we proceed from left to right. The number of numbers to the right of "3"
that are smaller than 1 is 2, so begin by setting n = 2*7!. The number
of numbers to the right of "7" that are smaller than 7 is 5, so compute
n := n + 5*6!. The number of numbers to the right of 1 that are smaller
than 1 is 0, so compute n := n + 0*5!. And so on. We get

n = 2*7! + 5*6! + 0*5! + 4*4! + 2*3! + 1*2! + 0*1!

as the index (assuming 12345678 is the 0th permutation).
--
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

From:	tchow at lsa.umich.edu
Subject:	Re: To generate all permutations of length N
Date:	21 Jan 2005 21:52:18 GMT

In article <41f160c0$0$559$b45e6eb0@senator-bedfellow.mit.edu>, I wrote:
<
< 37185426
<

That should have been, "...that are smaller than 3 is 2."

<
< n = 2*7! + 5*6! + 0*5! + 4*4! + 2*3! + 1*2! + 0*1!
<
--
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