Re: Consecutive Numbers



Nobody wrote:
"Maury Barbato" <mauriziobarbato@xxxxxxxx> wrote in message
news:5576058.15533.1244996553955.JavaMail.jakarta@xxxxxxxxxxxxxxxxxxxxxxxxxx
rossum wrote:

On Sat, 13 Jun 2009 14:02:36 EDT, Maury Barbato
<mauriziobarbato@xxxxxxxx> wrote:

Hello,
let k <= m <= n three positive integers.
Let S(k,m,n) be the number of subsets of
{1,...,n} with the following properties:

(1) S contains m elements

(2) S contains at least a sequence of at least k
consecutive numbers (that is, there exist j such
that j, j + 1, ..., j + k - 1 are in S)

I don't know the answer, except in the trivial
cases k = m or m = n. Do you have some idea?

Thank you for your attention.
My Best Regards,
Maury Barbato
Can you answer the question for S(1, m, n)?
Can you answer the question for S(2, m, n)?
Can you extrapolate from there?

rossum


Obviously, S(1,m,n) = (n choose m), but I don't
know how to find S(2,m,n). Some hint?

Thank you for your attention.
Maury Barbato

S(2,m,n) = C(n, m) - C(n+1-m, m).

But off-hand I can't figure out what S(3,m,n) is.

This all looks better in equal sized letters.


  If at first you don't succeed... Options   23
messages - Expand all  -  Translate all to Translated (View all
originals)   From: To: Cc:
Followup To: Add Cc | Add Followup-to | Edit Subject
Subject: Validation: For verification purposes please
type the characters you see in the picture below or the numbers you
hear by clicking the accessibility icon.   don  
View profile    More options Feb 20 2002, 5:23 pm d
Argh!!  Please, someone have pity and explain this to me? This recent
post added -more- to my confusion: =========== - Show quoted text -The
following is the original post that I got no response to :-
( =========== - Show quoted text - > whether a proposed solution
actually is a solution in polynomial time."] >(iii) there are a set of
NP problems that are shown to be equivalent, >(i.e., if a polynomial
time solution can be found for one, it can be >for all) >(iv) NP is
different from NP-complete (I don't understand this) [The following
makes it sound to me like (iv) would be true:] >"It turns out that a
lot of NP problems have 'equivalent' running >times. Specifically, an
NP problem is said to be NP-complete if the >existence of a polynomial
time solution for that problem implies that >all NP problems have a
polynomial time solution" [But this makes it sound more like (iv)
could be false: "The best that has been done to date is to prove that
a broad class of candidate non-P problems are all on the same
footing--- if any one of them can be solved in polynomial time, then
they all can. The problems involved here are said to have
'nondeterministic polynomial' running time: type NP." Is NP-complete a
subset of NP or are they the same?] >(v) Factorization is not -proven-
to be non-P or NP >"Finding the prime factors of a given integer is
also widely believed >to be non-P, too, but this has never been proved
either." >(vi) a general factorization method would not have any
bearing on the >"P=NP?" problem unless it was proven to be NP (or is
it NP-complete?) >>is proven true then it would mean that NP-complete
problems >>(and thus all other NP problems) would be solvable in
polynomial time and >>have faster solutions. >There again, it looks
like NP-complete is synonymous with NP??
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^? I would really
appreciate help in understanding the details of this, perhaps a
pointer to a reference that might possibly clear it up for me? - Show
quoted text -    Reply to author    Forward       Rate this post:
Text for clearing space . Discussion subject changed to "P
& NP (was Re: If at first you don't succeed...)" by Gerry
Myerson Gerry Myerson   View profile    More
options Feb 20 2002, 6:40 pm In article
<3c740f32.351159...@xxxxxxxxxxxxx>, d...@xxxxxxxxxxx wrote: > Argh!!
 Please, someone have pity and explain this to me? <snip> Let's go
with the definition that P is the problems solvable in polynomial time
& NP is the problems whose solutions are verifiable in polynomial
time. Note that NP contains P. The big question is whether P = NP. If
it does, then factorization (for example), which is certainly in NP
(because you can verify an alleged factorization real fast just by
multiplying), is also in P, and there goes the RSA encryption scheme.
There's a problem in NP called 3-SAT. This problem has the property
that every problem in NP can be translated efficiently into a 3-SAT
problem. It follows that if 3-SAT is in P then P = NP; take any
problem in NP, translate it efficiently into an instance of 3-SAT,
then solve. Because 3-SAT has this property, 3-SAT is said to be NP-
complete. There are lots of other problems that have been proved to
have this same property, thus if any one of them turns out to be in P,
then P = NP. The people who really know about these things seem to be
of the opinion that P doesn't equal NP. Let's take that as a working
hypothesis. Then there are three kinds of problems in NP; the ones
that are actually in P, the ones that are NP-complete, and the rest.
It's widely believed that factorization falls into the third group.
That is, it's believed that it's not in P, but even if it turns out
that it is in P that won't imply P = NP because there's no useful way
to translate every instance of 3-SAT into a factorization problem. I
hope that this is more-or-less correct (and if it isn't someone is
sure to correct it) & helpful. Gerry Myerson (ge...@xxxxxxxxxxxxxx)  
  Reply to author    Forward       Rate this post: Text for clearing
space . don   View profile    More options Feb
21 2002, 1:26 pm d First of all, Gerry, THANK YOU very
much for responding! On Thu, 21 Feb 2002 10:36:16 +1000, Gerry Myerson
<ge...@xxxxxxxxxxxxxx> wrote: >In article
<3c740f32.351159...@xxxxxxxxxxxxx>, d...@xxxxxxxxxxx wrote: >> Argh!!
 Please, someone have pity and explain this to me? ><snip> >Let's go
with the definition that P is the problems solvable in >polynomial
time & NP is the problems whose solutions are verifiable >in
polynomial time. Note that NP contains P. >The big question is whether
P = NP. If it does, then factorization Heh.  Y'all want to know
whether P=NP.  I just wanna know if NP=NP-complete, or what the
distinction is that I'm missing. :-) >(for example), which is
certainly in NP (because you can verify an >alleged factorization real
fast just by multiplying), is also in P, >and there goes the RSA
encryption scheme. Ian Stewart makes the distinction between non-P and
NP in the article cited in my previous post: "NP is not the same as
non-P. A problem is NP if you can check whether a proposed solution
actually is a solution in polynomial time." "Finding the prime factors
of a given integer is also widely believed to be non-P, too, but this
has never been proved either." Ok, so factoring is -believed- to be
non-P.  And -if it is- in non-P, then it is certainly NP because you
can verify the solution in polynomial time.  Now if it (factorization)
is proven to reduce to any given NP-complete problem, this would mean
it is also NP-complete and therefore also in NP (and non-P, if there
is a difference). >There's a problem in NP called 3-SAT. This problem
has the property >that every problem in NP can be translated
efficiently into a 3-SAT >problem. It follows that if 3-SAT is in P
then P = NP; take any >problem in NP, translate it efficiently into an
instance of 3-SAT, >then solve. -Every- problem in NP?  Or just the
other NP-complete ones?  OR is it the same thing?  It is sounding to
me like NP=NP-complete. >Because 3-SAT has this property, 3-SAT is
said to be NP-complete. >There are lots of other problems that have
been proved to have this >same property, thus if any one of them turns
out to be in P, then >P = NP. I can understand that.  NP-complete
problems are on the same footing. Can there exist problems that are NP
but are not NP-complete?  (If so, is this different than Stewart's
"non-P"?)  IF NP-complete problems having polynomial time solutions
imply that ALL problems in NP can be solved in polynomial time, then
why do we need to make the separate distinction of NP-complete. >The
people who really know about these things seem to be of the >opinion
that P doesn't equal NP. Let's take that as a working >hypothesis.
Then there are three kinds of problems in NP; the ones >that are
actually in P, the ones that are NP-complete, and the rest. Could it
be that what you're calling P, NP-complete, and "the rest" is what Ian
Stewart classifies as P, NP, and non-P?  If not, then there are four
categories of problems involved.  I don't know if I'm abusing the
terminology, but would one say that P is a subset of NP-complete, NP-
complete is a subset of NP, and NP is a subset of non-P? >It's widely
believed that factorization falls into the third group. >That is, it's
believed that it's not in P, but even if it turns out >that it is in P
that won't imply P = NP because there's no useful >way to translate
every instance of 3-SAT into a factorization problem. Yes, that makes
sense to me, thus my assumption about a general factorization method
not having any bearing on "P=NP?" unless it's proven NP-complete. >I
hope that this is more-or-less correct (and if it isn't someone is
sure to correct it) & helpful. It did seem to reinforce some of my
assumptions.  There are still two points I'm not comfortable with: (i)
I'm not seeing how a polynomial time solution for a subset of NP
problems could imply polynomial time solutions for -all- NP problems.
This is probably due to a flaw or gap in my own understanding.  (I
would love to learn more about this, if anyone could point me in the
right direction with references.) (ii) I think there's also still
terminology distinction I'm missing with regard to non-P/NP/NP-
complete.  I suspect that "non-P" may be "NP but not NP-complete"
although Stewart seems to make a distinction. Also, I sincerely
apologize if it's something trivial that I'm not understanding, as
I've posted several times seeking clarification. Thanks again, -don -
Show quoted text -    Reply to author    Forward       Rate this
post: Text for clearing space . Discussion subject
changed to "If at first you don't succeed..." by John
Rickard John Rickard   View profile    More
options Feb 21 2002, 1:44 pm d...@xxxxxxxxxxx
wrote: : Argh!!  Please, someone have pity and explain this to me? :
The following is the original post that I got no response to :-( :
After reading this thread and this: : > : >http://claymath.org/
prizeproblems/milliondollarminesweeper.htm : > : >I am still confused.
 Could someone please verify or correct my : >understanding: : > : >
(i) non-P refers to any problem that's not solvable in polynomial time
Yes. : >(ii) a problem may be non-P but is NP -only if- solutions to
that : >problem can be verified in polynomial time Not strictly
accurate, but close enough.  But note that an NP problem does not need
to be non-P: indeed, all problems in P are also in NP. : >(iii) there
are a set of NP problems that are shown to be equivalent, Namely, NP-
complete. : >(i.e., if a polynomial time solution can be found for
one, it can be : >for all) Not strictly accurate, but close enough.
 (Though if a polynomial-time solution can be found for any NP-
complete problem, then one can be found for any NP problem, not just
for any NP-complete problem.) : >(iv) NP is different from NP-complete
(I don't understand this) NP-complete is a subset of NP; the NP-
complete problems are the hardest problems in NP. : [But this makes it
sound more like (iv) could be false: : : "The best that has been done
to date is to prove that a broad class of : candidate non-P problems
are all on the same footing--- if any one of : them can be solved in
polynomial time, then they all can. The problems : involved here are
said to have 'nondeterministic polynomial' running : time: type NP."
The last sentence is misleading: it is true that the problems involved
are in NP, but it's *not* true (although the quotation might seem to
suggest it) that the class of problems is exactly NP. : >(v)
Factorization is not -proven- to be non-P or NP It *is* NP: given a
factorization of a number, one can verify it in polynomial time by
multiplying the factors together.  It is not known (nor, I think,
believed) to be NP-complete. (Note 1: That's assuming that one just
wants to find some non-trivial factorization of a number that's known
not to be prime.  If one wants a complete factorization into primes,
it's a bit more complicated, but there is a method of providing a
certificate that a number is prime that can be checked in polynomial
time, so that problem is in NP too. Note 2: Actually, factorization is
the wrong type of problem to be in NP: NP consists of decision
problems, where the answer is "yes" or "no".  But the related problem
"Does n have a factor m in the range a < m < b?" is in NP, and if that
problem could be solved in polynomial time then one could factor in
polynomial time by binary search.) : >(vi) a general factorization
method would not have any bearing on the : >"P=NP?" problem unless it
was proven to be NP (or is it NP-complete?) I'm not sure what you
intend "it" to refer to.  It is true that a general factorization
method would not have any bearing on "P=NP?", since factorization is
not known (or believed) to be NP-complete. : >>is proven true then it
would mean that NP-complete problems : >>(and thus all other NP
problems) would be solvable in polynomial time and : >>have faster
solutions. : > : >There again, it looks like NP-complete is synonymous
with NP?? : ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^? No,
the point is that NP-complete problems are the hardest in NP, and if
any NP-complete problem can be solved in polynomial time then all NP
problems can be solved in polynomial time. -- John Rickard  
<jrick...@xxxxxxxxxxxxxxxxxxx>     Reply to author    Forward  
    Rate this post: Text for clearing space . Discussion
subject changed to "P & NP (was Re: If at first you don't succeed...)"
by step...@xxxxxxxxxxxxxx stephen   View profile
   More options Feb 21 2002, 2:40 pm
d...@xxxxxxxxxxx wrote: : It did seem to reinforce some of my
assumptions.  There are still two : points I'm not comfortable with: :
(i) I'm not seeing how a polynomial time solution for a subset of NP :
problems could imply polynomial time solutions for -all- NP
problems. : This is probably due to a flaw or gap in my own
understanding.  (I : would love to learn more about this, if anyone
could point me in the : right direction with references.) A polynomial
time solution to an NP-complete problem implies a polynomial time
solution to all problems in NP.  Suppose you find a polynomial
solution for problem X, and X is NP-complete. Because X is NP-
complete, you can transform any problem in NP into X in polynomial
time.  So to solve any problem in NP, first transform it into X, and
then solve X. : (ii) I think there's also still terminology
distinction I'm missing : with regard to non-P/NP/NP-complete.  I
suspect that "non-P" may be : "NP but not NP-complete" although
Stewart seems to make a distinction. non-P means that it cannot be
solved in polynomial class.  NP is a subset of non-P, and NP-complete
is a subset of NP.  There are problems that are (seemingly) harder
than the hardest problems in NP. Maybe an example would help.
 Consider a problem Z that requires n^{log n} time to solve.  This
problem is not in P because n^{log n} grows faster than any
polynomial.   If a solution to Z can be verified in polynomial time,
then Z is in NP.   If Z was NP-complete, then all problems in NP could
be solved in f(n) n^{log n} time, where f(n) is a polynomial that
depends on the particular problem.  It is still possible that there is
a problem Y that requires 2^n time, and 2^n> f(n) n^{log n} for any
polynomial f(n).  The problem Y is non-P, but it is not in NP. If Z is
in NP, but not NP-complete, then there may be problems in NP that
require more than f(n) n^{log n} time to solve.  There may be problems
in NP that require 2^n time. Of course, the distinctions between P,
NP, and NP-complete all vanish if P=NP. : Also, I sincerely apologize
if it's something trivial that I'm not : understanding, as I've posted
several times seeking clarification. : Thanks again, : -don I hope
this makes sense. Stephen     Reply to author    Forward       Rate
this post: Text for clearing space . Discussion subject
changed to "If at first you don't succeed..." by
d...@xxxxxxxxxxx don   View profile    More
options Feb 21 2002, 3:25 pm d On 21 Feb 2002 18:43:54
+0000 (GMT), John Rickard <j...@xxxxxxxx> wrote: >d...@xxxxxxxxxxx
wrote: >: >(ii) a problem may be non-P but is NP -only if- solutions
to that >: >problem can be verified in polynomial time >Not strictly
accurate, but close enough.  But note that an NP problem >does not
need to be non-P: indeed, all problems in P are also in NP. Heh.  The
"not strictly accurate" is what is messing me up to begin with. :-)
 PLEASE, if you know of any references that would explain this to me
strictly accurately, I would appreciate them.  I am wondering whether
or not an algorithm book would explain it all in nice detail. >: >
(iii) there are a set of NP problems that are shown to be equivalent,
Namely, NP-complete. >: >(i.e., if a polynomial time solution can be
found for one, it can be >: >for all) >Not strictly accurate, but
close enough.  (Though if a polynomial-time >solution can be found for
any NP-complete problem, then one can be >found for any NP problem,
not just for any NP-complete problem.) Yes, I was beginning to gather
this, though I don't understand it. >: >(iv) NP is different from NP-
complete (I don't understand this) >NP-complete is a subset of NP; the
NP-complete problems are the >hardest problems in NP. Aha!  My feeble
brain begins to understand. >: [But this makes it sound more like (iv)
could be false: >: >: "The best that has been done to date is to prove
that a broad class of >: candidate non-P problems are all on the same
footing--- if any one of >: them can be solved in polynomial time,
then they all can. The problems >: involved here are said to have
'nondeterministic polynomial' running >: time: type NP." >The last
sentence is misleading: it is true that the problems involved >are in
NP, but it's *not* true (although the quotation might seem to >suggest
it) that the class of problems is exactly NP. Yes.  Thank you! >: >(v)
Factorization is not -proven- to be non-P or NP >It *is* NP: given a
factorization of a number, one can verify it in >polynomial time by
multiplying the factors together.  It is not known >(nor, I think,
believed) to be NP-complete. Yes, I'm pretty sure I've read elsewhere
that factorization is not believed to be of the difficulty of NP-
complete problems. "Finding the prime factors of a given integer is
also widely believed to be non-P, too, but this has never been proved
either." So if it is believed to be non-P but not NP, then is the
relationship of NP to non-P like NP-complete to NP?  That is, is NP a
subset of "tougher" problems in non-P? >(Note 1: That's assuming that
one just wants to find some non-trivial >factorization of a number
that's known not to be prime.  If one wants >a complete factorization
into primes, it's a bit more complicated, but >there is a method of
providing a certificate that a number is prime >that can be checked in
polynomial time, so that problem is in NP too. >Note 2: Actually,
factorization is the wrong type of problem to be in >NP: NP consists
of decision problems, where the answer is "yes" or >"no".  But the
related problem "Does n have a factor m in the range >a < m < b?" is
in NP, and if that problem could be solved in >polynomial time then
one could factor in polynomial time by binary >search.) Ah, that makes
lots more sense in terms of how the problems are classified.   >: >
(vi) a general factorization method would not have any bearing on the
: >"P=NP?" problem unless it was proven to be NP (or is it NP-
complete?) >I'm not sure what you intend "it" to refer to.  It is true
that a >general factorization method would not have any bearing on
"P=NP?", >since factorization is not known (or believed) to be NP-
complete. Right.  I didn't understand the NP/NP-complete relationship.
 Now that I understand that NP-complete probs are the tough ones, it
makes a lot more sense. >: >>is proven true then it would mean that NP-
complete problems >: >>(and thus all other NP problems) would be
solvable in polynomial time and >: >>have faster solutions. >: > >:
There again, it looks like NP-complete is synonymous with NP?? >:
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^? >No, the point is
that NP-complete problems are the hardest in NP, and >if any NP-
complete problem can be solved in polynomial time then all >NP
problems can be solved in polynomial time. I understand that point
now.  Thank you so much for all the helpful information!!! -don - Show
quoted text -    Reply to author    Forward       Rate this post:
Text for clearing space . Discussion subject changed to "P
& NP (was Re: If at first you don't succeed...)" by Gerry
Myerson Gerry Myerson   View profile    More
options Feb 21 2002, 5:35 pm In article <a53h9l
$7p...@xxxxxxxxxxxxxxxxxx>, step...@xxxxxxxxxxxxxx wrote: > non-P
means that it cannot be solved in polynomial class.  NP is > a subset
of non-P, and NP-complete is a subset of NP.   I haven't seen the
terminology "non-P" before, but if it means what you say it means - if
it means all the problems that are not in P - then NP is not a subset
of non-P. NP contains P - trivially - so NP can't be a subset of non-P
(unless P is empty, which it isn't). Gerry Myerson
(ge...@xxxxxxxxxxxxxx)     Reply to author    Forward       Rate this
post: Text for clearing space . Gerry Myerson  
View profile    More options Feb 21 2002, 5:55 pm
In article <3c751f3e.420804...@xxxxxxxxxxxxx>, d...@xxxxxxxxxxx wrote:
(i) I'm not seeing how a polynomial time solution for a subset of NP
problems could imply polynomial time solutions for -all- NP
problems. > This is probably due to a flaw or gap in my own
understanding.  (I > would love to learn more about this, if anyone
could point me in the > right direction with references.) The reason
you're not seeing it is that it's not easy to see. It was a terrific
piece of work to show that every instance of every possible NP problem
could be efficiently translated into an instance of the problem 3-SAT.
It's not at all obvious; it really takes some clever ideas and the
energy to follow them through. The standard reference on these matters
has long been Garey and Johnson, Computers and Intractability,
published by Freeman in 1978. A lot has been done in the years since,
but the questions you're asking are all answered in Garey & Johnson. >
(ii) I think there's also still terminology distinction I'm missing >
with regard to non-P/NP/NP-complete.  I suspect that "non-P" may be >
"NP but not NP-complete" although Stewart seems to make a distinction.
I really should read the Stewart piece before I comment on this, but I
can't imagine that anyone would use "non-P" to mean "NP but not NP-
complete." The part of NP that is not NP-complete includes P
(assuming, as always, that P = NP is false), so it seems perverse to
call it "non-P." I can imagine two reasons a person might come up with
the terminology "non-P." One is to refer to the complement of P in the
set of all problems. This would include things that aren't even in NP,
problems where it takes (say) exponential time just to verify a
solution. The other use I could imagine for the term "non-P" is the
complement of P in NP. Look at Stewart again and see whether he
doesn't mean one of these.     Reply to author    Forward       Rate
this post: Text for clearing space . stephen  
View profile    More options Feb 21 2002, 6:05 pm
Gerry Myerson <ge...@xxxxxxxxxxxxxx> wrote: : In article <a53h9l
$7p...@xxxxxxxxxxxxxxxxxx>, step...@xxxxxxxxxxxxxx : wrote: :> non-P
means that it cannot be solved in polynomial class.  NP is :> a subset
of non-P, and NP-complete is a subset of NP.   : I haven't seen the
terminology "non-P" before, but if it means what : you say it means -
if it means all the problems that are not in P - then : NP is not a
subset of non-P. NP contains P - trivially - so NP can't be : a subset
of non-P (unless P is empty, which it isn't). : Gerry Myerson
(ge...@xxxxxxxxxxxxxx) Yeah, you are right.  I meant to say that NP-P
is a subset of non-P.  I have personally not seen the terminology "non-
P" either, but it does seem to be a common misconception that NP is
the set of problems that are not in P. Stephen     Reply to
author    Forward       Rate this post: Text for clearing
space . Gerry Myerson   View profile    More
options Feb 21 2002, 6:15 pm .
don   View profile    More options Feb 21 2002, 7:00 pm
d On 21 Feb 2002 19:20:21 GMT, step...@xxxxxxxxxxxxxx wrote:
A polynomial time solution to an NP-complete problem implies >a
polynomial time solution to all problems in NP.  Suppose >you find a
polynomial solution for problem X, and X is NP-complete. >Because X is
NP-complete, you can transform any problem in NP >into X in polynomial
time.  So to solve any problem in NP, >first transform it into X, and
then solve X. Got it.  I didn't realize that the NP-complete problems
were the "toughest" NP problems; I was thinking about it quite
backwards, specifically that if a problem wasn't NP-complete it would
be tougher to solve. >non-P means that it cannot be solved in
polynomial class.  NP is >a subset of non-P, and NP-complete is a
subset of NP.  There >are problems that are (seemingly) harder than
the hardest problems >in NP. >Maybe an example would help.  Consider a
problem Z that >requires n^{log n} time to solve.  This problem is not
in P >because n^{log n} grows faster than any polynomial.   >If a
solution to Z can be verified in polynomial time, then Z is in NP.  
If Z was NP-complete, then all problems in NP could be solved >in f
(n) n^{log n} time, where f(n) is a polynomial that depends on >the
particular problem.  It is still possible that there is a problem Y
that requires 2^n time, and 2^n> f(n) n^{log n} for any polynomial >f
(n).  The problem Y is non-P, but it is not in NP. With ya so far I
think.  The last bit here threw me at first; I thought you were saying
Y being not in NP had something to do with it's 2^n> f(n) n^{log n}
running time, but it does not.  The only criteria deciding if a
problem is NP or not is whether a solution to it can be verified in
polynomial time. >If Z is in NP, but not NP-complete, then there may
be problems in NP >that require more than f(n) n^{log n} time to
solve.  There may >be problems in NP that require 2^n time. So even
though a solution could be checked in polynomial time, the problem
itself could require 2^n time, making it "harder" to solve than the Z
in your example. >Of course, the distinctions between P, NP, and NP-
complete all vanish >if P=NP. >I hope this makes sense. Most of it
does, and the rest probably will when I read a bit more. Thank you
very much for the info, -don - Show quoted text -    Reply to
author    Forward       Rate this post: Text for clearing
space . don   View profile    More options Feb
21 2002, 7:04 pm d On Fri, 22 Feb 2002 09:32:32 +1000,
Gerry Myerson <ge...@xxxxxxxxxxxxxx> wrote: >In article <a53h9l
$7p...@xxxxxxxxxxxxxxxxxx>, step...@xxxxxxxxxxxxxx >wrote: >> non-P
means that it cannot be solved in polynomial class.  NP is >> a subset
of non-P, and NP-complete is a subset of NP.   >I haven't seen the
terminology "non-P" before, but if it means what >you say it means -
if it means all the problems that are not in P - then >NP is not a
subset of non-P. NP contains P - trivially - so NP can't be >a subset
of non-P (unless P is empty, which it isn't). Good point.  That didn't
make sense to me either. -don - Show quoted text -    Reply to
author    Forward       Rate this post: Text for clearing
space . don   View profile    More options Feb
21 2002, 7:52 pm d On Fri, 22 Feb 2002 09:50:41 +1000,
Gerry Myerson - Show quoted text ->> (ii) I think there's also still
terminology distinction I'm missing >> with regard to non-P/NP/NP-
complete.  I suspect that "non-P" may be >> "NP but not NP-complete"
although Stewart seems to make a distinction. >I really should read
the Stewart piece before I comment on this, >but I can't imagine that
anyone would use "non-P" to mean "NP but >not NP-complete." The part
of NP that is not NP-complete includes >P (assuming, as always, that P
= NP is false), so it seems perverse >to call it "non-P." Yes, my
understanding was incorrect in several places, which had me piecing it
together even more incorrectly. >I can imagine two reasons a person
might come up with the terminology >"non-P." One is to refer to the
complement of P in the set of all >problems. This would include things
that aren't even in NP, problems >where it takes (say) exponential
time just to verify a solution. The >other use I could imagine for the
term "non-P" is the complement of P >in NP. Look at Stewart again and
see whether he doesn't mean one of >these. It's obvious now that it's
the former. -don     Reply to author    Forward       Rate this
post: Text for clearing space . stephen   View
profile    More options Feb 21 2002, 8:00 pm
d . don   View profile    More options Feb
21 2002, 8:39 pm d On 22 Feb 2002 00:44:51 GMT,
step...@xxxxxxxxxxxxxx wrote: - Show quoted text -time solution for Z
implies that problems requiring 2^n time would not be in NP and, of
course, P=NP and "the distinctions between P, NP, and NP-complete all
vanish." >At the moment, I do not think there is an easy way to show
that a >problem is not in NP.  To show that it is in NP, I just need
to show that >I can verify the solution in polynomial time.  To show
that it is >not in NP, I have to show that there is no way to verify a
solution >in polynomial time.  It is much easier to demonstrate that
something >can be done than to demonstrate that it cannot be done.
Hmm.  That last sentence sounds like a good quote.  For some reason it
sounds incredibly optimistic to my logic-deprived brain.  It also goes
quite well with things I have heard in response to certain of my own
achievements:  "He was too dumb to realize that he shouldn't have been
able to do it."  ;-) -don - Show quoted text -    Reply to
author    Forward       Rate this post: Text for clearing
space . stephen   View profile    More options
Feb 21 2002, 9:00 pm d...@xxxxxxxxxxx wrote: : On 22
Feb 2002 00:44:51 GMT, step...@xxxxxxxxxxxxxx
wrote: :>d...@xxxxxxxxxxx wrote: :>:>If Z was NP-complete, then all
problems in NP could be solved :>:>in f(n) n^{log n} time, where f(n)
is a polynomial that depends on :>:>the particular problem.  It is
still possible that there is a problem Y :>:>that requires 2^n time,
and 2^n> f(n) n^{log n} for any polynomial :>:>f(n).  The problem Y is
non-P, but it is not in NP. :> :>: With ya so far I think.  The last
bit here threw me at first; I :>: thought you were saying Y being not
in NP had something to do with :>: it's 2^n> f(n) n^{log n} running
time, but it does not.  The only :>: criteria deciding if a problem is
NP or not is whether a solution to :>: it can be verified in
polynomial time. :> :>But if we knew that we could solve all problems
in NP in :>f(n) n^{log n} time, then we would know that any problem
that :>required 2^n time could not be in NP.  That is a big if. :
Gotcha.  Assuming Z is NP-complete and a (for example) f(n) n^{log
n} : time solution for Z implies that problems requiring 2^n time
would not : be in NP and, of course, P=NP and "the distinctions
between P, NP, and : NP-complete all vanish." No.  n^{log n} is not a
polynomial.  That is why I chose it. If a problem required n^{log n}
time, it would not be in P. If it was NP-complete, we could solve all
NP problems in f(n) n^{log n} time (where f(n) is a polynomial), and
any problem that required more than f(n) n^{log n} time would not be
in NP.   :>At the moment, I do not think there is an easy way to show
that a :>problem is not in NP.  To show that it is in NP, I just need
to show that :>I can verify the solution in polynomial time.  To show
that it is :>not in NP, I have to show that there is no way to verify
a solution :>in polynomial time.  It is much easier to demonstrate
that something :>can be done than to demonstrate that it cannot be
done. : Hmm.  That last sentence sounds like a good quote.  For some
reason it : sounds incredibly optimistic to my logic-deprived brain.
 It also goes : quite well with things I have heard in response to
certain of my own : achievements:  "He was too dumb to realize that he
shouldn't have been : able to do it."  ;-) : -don In some ways it is
optimistic, I suppose, but it is a simple fact.  To prove something is
doable, I just need to do it. To prove something cannot be done, I
have to show that no matter what you try, it cannot work.  To prove
that white crows exist, I just have to find one white crow.  To prove
there that no white crows exist is not so easy. Stephen     Reply to
author    Forward       Rate this post: Text for clearing
space . Herman Rubin   View profile    More
options Feb 22 2002, 9:30 am In article
<gerry-2F7162.10361621022002@[137.111.1.11]>, Gerry Myerson
 <ge...@xxxxxxxxxxxxxx> wrote: >In article
<3c740f32.351159...@xxxxxxxxxxxxx>, d...@xxxxxxxxxxx wrote: >> Argh!!
 Please, someone have pity and explain this to me? <snip> >Let's go
with the definition that P is the problems solvable in >polynomial
time & NP is the problems whose solutions are verifiable >in
polynomial time. Note that NP contains P. >The big question is whether
P = NP. If it does, then factorization >(for example), which is
certainly in NP (because you can verify an >alleged factorization real
fast just by multiplying), is also in P, >and there goes the RSA
encryption scheme. This last statement is false.  That something can
be done in polynomial time gives no information on the degree of the
polynomial or its coefficients.  If there is a method to factor a
number of n digits in time n^1000, the safety of RSA encryption would
not be affected in the least. >There's a problem in NP called 3-SAT.
This problem has the property >that every problem in NP can be
translated efficiently into a 3-SAT >problem. Change "efficiently" to
"in polynomial time", here and in the next statement.         It
follows that if 3-SAT is in P then P = NP; take any - Show quoted text
->This address is for information only.  I do not claim that these
views are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette
IN47907-1399 hru...@xxxxxxxxxxxxxxx         Phone: (765)494-6054  
FAX: (765)494-0558     Reply to author    Forward       Rate this
post: Text for clearing space . don   View
profile    More options Feb 22 2002, 10:41 am d On
22 Feb 2002 09:21:22 -0500, hru...@xxxxxxxxxxxxxxxxxxxx (Herman Rubin)
wrote: >In article <gerry-2F7162.10361621022002@[137.111.1.11]>,
Gerry Myerson  <ge...@xxxxxxxxxxxxxx> wrote: >>The big question is
whether P = NP. If it does, then factorization >>(for example), which
is certainly in NP (because you can verify an >>alleged factorization
real fast just by multiplying), is also in P, >>and there goes the RSA
encryption scheme. >This last statement is false.  That something can
be done >in polynomial time gives no information on the degree of >the
polynomial or its coefficients.  If there is a method >to factor a
number of n digits in time n^1000, the safety >of RSA encryption would
not be affected in the least. Interesting point.  Say there is an -
efficient- poly time factorization method found.  Surely RSA looks
into "backup" methods. I remember reading something about non-
factorization based encryption methods.  Anyone know if they have
something close to as effective as RSA encryption is believed to be? -
don     Reply to author    Forward       Rate this post: Text for
clearing space . don   View profile    More
options Feb 22 2002, 10:50 am d On 22 Feb 2002
01:41:39 GMT, step...@xxxxxxxxxxxxxx wrote: >d...@xxxxxxxxxxx wrote:
: On 22 Feb 2002 00:44:51 GMT, step...@xxxxxxxxxxxxxx wrote: >:
Gotcha.  Assuming Z is NP-complete and a (for example) f(n) n^{log n}
: time solution for Z implies that problems requiring 2^n time would
not >: be in NP and, of course, P=NP and "the distinctions between P,
NP, and >: NP-complete all vanish." >No.  n^{log n} is not a
polynomial.  That is why I chose it. >If a problem required n^{log n}
time, it would not be in P. >If it was NP-complete, we could solve all
NP problems in f(n) n^{log n} >time (where f(n) is a polynomial), and
any problem that required more >than f(n) n^{log n} time would not be
in NP.   Ok, I see.  The problem requiring f(n) n^{log n} time simply
implies that all NP can be solved that quickly, and anything "more
difficult" would be excluded from NP.  The only way P=NP is if the
problem Z in your example ran in f(n) time. -don     Reply to
author    Forward       Rate this post: Text for clearing
space . Matan Ziv-Av   View profile    More
options Feb 22 2002, 6:33 pm On Thu, 21 Feb 2002
10:36:16 +1000, Gerry Myerson wrote: >  Let's go with the definition
that P is the problems solvable in >  polynomial time & NP is the
problems whose solutions are verifiable >  in polynomial time. Note
that NP contains P. >  The big question is whether P = NP. If it does,
then factorization >  (for example), which is certainly in NP (because
you can verify an >  alleged factorization real fast just by
multiplying), is also in P, >  and there goes the RSA encryption
scheme. Saying that ("there goes RSA...") is common, but it is wrong.
Assume that there is an algorithm that factorizes a number of length n
(bits) in n^1000 steps. It shows that P=NP, but it does not help in
factoring a 256 bit key in a reasonable time. On the other hand if
there is a proof that P ir not equal to NP, by finding an algorithm
for factorizing in 2^(n/10000) steps, and proving that it is fastest -
there goes RSA. -- Matan Ziv-Av.                        
ma...@xxxxxxxxxxx     Reply to author    Forward       Rate this
post: Text for clearing space . Keith Ramsay  
View profile    More options Feb 25 2002, 2:23 am
In article <a53h9l$7p...@xxxxxxxxxxxxxxxxxx>, step...@xxxxxxxxxxxxxx
writes: |Maybe an example would help.  Consider a problem Z that |
requires n^{log n} time to solve.  This problem is not in P |because n^
{log n} grows faster than any polynomial.   | |If a solution to Z can
be verified in polynomial time, then Z is in NP.   | |If Z was NP-
complete, then all problems in NP could be solved |in f(n) n^{log n}
time, where f(n) is a polynomial that depends on |the particular
problem. Shouldn't that be f(n)^{log f(n)} or n^{C log n} for some C
depending upon the problem? The reduction is allowed to expand the
size of the problem, although the length is still bounded by a
polynomial in terms of the original length. Showing that a problem is
NP-complete is one of the standard ways to get evidence that it's not
in P, since it seems unlikely that P=NP. Likewise, showing that a
problem is complete for some class of problems that we think is larger
than NP is a way to get evidence that it isn't in NP. For example,
PSPACE, the class of problems that can be solved in storage space
bounded by a polynomial, is almost certainly a larger class than NP,
and we know of some PSPACE-complete problems. A number
SJ wrote:
matan@xxxxxxxxxxx (Matan Ziv-Av) wrote in message news:<slrna7dlav.9b3.matan@xxxxxxxxxx>...
On Thu, 21 Feb 2002 10:36:16 +1000, Gerry Myerson wrote:

Let's go with the definition that P is the problems solvable in
polynomial time & NP is the problems whose solutions are verifiable
in polynomial time. Note that NP contains P.

The big question is whether P = NP. If it does, then factorization
(for example), which is certainly in NP (because you can verify an
alleged factorization real fast just by multiplying), is also in P,
and there goes the RSA encryption scheme.

Saying that ("there goes RSA...") is common, but it is wrong.
Assume that there is an algorithm that factorizes a number of length
n (bits) in n^1000 steps. It shows that P=NP, but it does not help
in factoring a 256 bit key in a reasonable time. On the other hand
if there is a proof that P ir not equal to NP, by finding an algorithm
for factorizing in 2^(n/10000) steps, and proving that it is fastest -
there goes RSA.

Can someone also explain how NP-Hard is different from NP-complete?
specifically my questions are
1) Is NP-complete defined only for decision problems and NP-Hard for
all optimization problems?
2) Is NP-complete a subset of NP-Hard? eg. Traveling salesman problem?

thanks
SJ

P=NP

We proceed by induction on the polynomial P Base case trivial (by
symbolic evaluation)

ax P " = N ax P "

Rippling in the step case is blocked. Proceed by case split on N Zero
branch Weak fertilise

ax(NP)=0 (ax P) "

Speculate lemma associativity of times-which instantiates N to 0. Now
treat sucessor branch

axnnnn...
axnnnn...
axnnnn...
P " P " P " = = =0( axnnnn...nn.n... P=P which follows by reflexivity
of equality¤ axnnn... P " P " (Suc0)axnnn... ) P.

MeAmI.org
.

Relevant Pages

  • Re: NP-complete and NP-Hard?
    ... > I don't quite understand NP-Complete and NP-Hard problem, ... NP is the class of problems that can be solved in polynomial time (in ... that you need exponential time to solve an NP problem - there might be ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... Radoslaw Hofman wrote: ... If there is a UP set that is NP-complete, ... he may solve any TSP instance in polynomial time then he can solve any ... (unique solution and polynomially solvable) ...
    (comp.theory)
  • NP-Complete Definition
    ... If B is NP-Complete and B is polynomial-time-reducible to C (where C ... Suppose that the reduction R reduces B to C in polynomial time, ... Maybe the original input to B was of size n, ... The reduction occurs in polynomial time, ...
    (comp.theory)
  • Re: basic query regarding NP Complete...
    ... is a set of NP-Complete problems. ... Forgive me if I sound a little stupid.. ... I suppose cookes ... in NP can be converted in polynomial time into the problem you are claiming ...
    (comp.theory)
  • Re: JSH: Easy math, easy solution
    ... >website and do their prime factorization challenge. ... All of these steps can be performed in polynomial time on a classical ... time using both a quantum computer and a classical computer. ...
    (sci.math)