P, NP, NP Complete, Intractable in layman terms?

  • Permalink
  • submit to reddit
  • Email
  • Follow


The news of Vinay Deolalikar possibly proving that P not-equals NP
prompted me to again attempt to come up with a layman definition of
these terms (not the formal definitions, which are confusing and
circular).  Kindly correct me if I am wrong.

       1). P: A problem that can be solved efficiently

       2). NP: A problem that can be verified efficiently

       3). NP Complete: A class of related problems that can be
efficiently verified but for which no efficient solution has been
found yet (and probably none exists).  If an efficient solution can be
found for even one of these problems, they can all be solved
efficiently.

       4). NP Hard: A really hard problem to solve, may or may not be
efficiently verifiable.

       5). Intractable: A problem with provably no solution (e.g.
Turing Halting Problem)

I referred to the following websites for this:
       1). http://web.mit.edu/newsoffice/2009/explainer-pnp.html

       2). http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext

       3). http://www.aolnews.com/surge-desk/article/p-np-wtf-a-short-guide-to-understanding-vinay-deolalikars-mat/19586401

       4). http://mathworld.wolfram.com/NP-HardProblem.html

Thanks,
Zahid
0
Reply zahidfaizal (17) 8/12/2010 12:31:01 AM

See related articles to this posting


Zahid Faizal <zahidfaizal@canada.com>, on 11/08/2010 17:31:01, wrote:

> The news of Vinay Deolalikar possibly proving that P not-equals NP
> prompted me to again attempt to come up with a layman definition of
> these terms (not the formal definitions, which are confusing and
> circular).  Kindly correct me if I am wrong.
>
>         1). P: A problem that can be solved efficiently
>
>         2). NP: A problem that can be verified efficiently
>
>         3). NP Complete: A class of related problems that can be
> efficiently verified but for which no efficient solution has been
> found yet (and probably none exists).  If an efficient solution can be
> found for even one of these problems, they can all be solved
> efficiently.
>
>         4). NP Hard: A really hard problem to solve, may or may not be
> efficiently verifiable.
>
>         5). Intractable: A problem with provably no solution (e.g.
> Turing Halting Problem)

I don't know if you got them perfectly, but reading your list I was able 
to give more sense to what I've been able to understand on my own about 
the subject.

Thanks for posting it, it helped me completing the whole rough picture.

-- 
  FSC - http://userscripts.org/scripts/show/59948
  http://fscode.altervista.org - http://sardinias.com
0
Reply entuland (631) 8/12/2010 1:00:40 AM

On 08/11/2010 08:31 PM, Zahid Faizal wrote:
> The news of Vinay Deolalikar possibly proving that P not-equals NP
> prompted me to again attempt to come up with a layman definition of
> these terms (not the formal definitions, which are confusing and
> circular).  Kindly correct me if I am wrong.
>
>         1). P: A problem that can be solved efficiently
>
>         2). NP: A problem that can be verified efficiently

Here, there are two qualifiers that need to be made:
1. P and NP (in addition to NP-complete) are classes of only decision 
problems--those for which the algorithm will print either YES or NO.

2. "Efficiently" is a vague word. The key requirement here is that the 
algorithm must be bounded by polynomial time in the size of the input, 
but I would struggle to come up with a description that is concise, 
accurate, and nonmathematical. Perhaps one way of thinking about it is 
an algorithm is efficient if doubling the size of the input multiplies 
run time by a constant as opposed to squaring it (or worse).

>         3). NP Complete: A class of related problems that can be
> efficiently verified but for which no efficient solution has been
> found yet (and probably none exists).  If an efficient solution can be
> found for even one of these problems, they can all be solved
> efficiently.

NP-complete is the class of all (decision) problems for which any NP 
problem would be "merely" a special case. In other words, solving it 
"efficiently" allows you to solve any problem in NP "efficiently." Note 
that this is a case where the common connotation is a bit wrong: 
applying all reductions the addition problem to subset sum leads to a 
problem of size ~O(n^48), which is easily intractable.

Another way of looking at many NP-complete problems (or NP-hard in 
general) is that they are problems where our known algorithms boil down 
to, in essence, "try a large fraction of all possible solutions", where 
the space of possible solutions is ~O(n!) or greater.

>         4). NP Hard: A really hard problem to solve, may or may not be
> efficiently verifiable.

NP-hard is a generalization of NP-complete. Unlike the other three 
mentioned classes, NP-hard includes non-decision problems. Roughly 
speaking, a problem is NP-hard if you can use it to solve an NP-complete 
problem. An example: the boolean satisfiability problem asks if there 
exists an assignment for variables that satisfies a given equation; this 
problem is NP-complete. A related problem is to, given such an equation, 
find an assignment (if it exists) that would satisfy the equation. This 
one is NP-hard: clearly, being able to solve the latter allows you to 
solve the former.

That example is particularly poignant for another reason: though the 
functional problem (find the assignment) and the decision problem (is 
there an assignment?) are often treated as the same problem, it does 
indicate that it is possible to show that P=NP and still have it be 
useless in practical application. One can consider that the solution 
could be a nonconstructive algorithm: it can tell you that a solution 
exists but it gives no insight into what the solution would be.

Consider the relation between primality testing and factoring. All fast 
algorithms that I know of can show that a number is not prime but will 
not deduce a factor of the number in the process.

>         5). Intractable: A problem with provably no solution (e.g.
> Turing Halting Problem)

On this, you are quite wrong. A problem with no solution is called 
"undecidable". Intractable problems are those that we cannot solve 
quickly--not in the asymptotic polynomial/exponential case, but in the 
raw time case. A problem that has runtime n^5 with a low constant 
coefficient is easily tractable while one with 1e100 * n^2 is easily 
intractable, even though the latter is asymptotically preferable.

An interesting related note is that all of these cases are decided for 
the worst case solution, so it's possible that a solution exists which 
is tractable for many "real" applications but intractable in a few 
special worst cases. This includes, notably, undecidable problems: it is 
possible to solve an undecidable problem in many common cases, just not 
for every single case.

-- 
Beware of bugs in the above code; I have only proved it correct, not 
tried it. -- Donald E. Knuth
0
Reply Pidgeot18 (1520) 8/12/2010 1:54:06 AM

Keeping in mind that this is for the layman...

In article <9dcc8a5d-c1de-48d0-bf8c-62e86e8f0047@x18g2000pro.googlegroups.com>,
Zahid Faizal  <zahidfaizal@canada.com> wrote:
>       1). P: A problem that can be solved efficiently

Reasonable.

>       2). NP: A problem that can be verified efficiently

Reasonable, though I might phrase it, "a problem whose solutions may not
be easy to find, but whose solutions are easily recognizable as correct
once they are found."

>       3). NP Complete: A class of related problems that can be
>efficiently verified but for which no efficient solution has been
>found yet (and probably none exists).  If an efficient solution can be
>found for even one of these problems, they can all be solved
>efficiently.

Reasonable, though I would phrase it, "The hardest problems in NP.  If an
efficient solution can be found for even one of these problems, then all
problems in NP can be solved efficiently."

>       4). NP Hard: A really hard problem to solve, may or may not be
>efficiently verifiable.

Not bad, but I would say, "A problem whose efficient solution would lead
to the efficient solution of every problem in NP, but which may not itself
be in NP.  If an NP-hard problem is in NP then it is NP-complete."

>       5). Intractable: A problem with provably no solution (e.g.
>Turing Halting Problem)

This term is not strictly speaking a technical term and is used in different
ways by different people.  Some people use it the way you say, but others
just use it to mean "hard."
-- 
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
0
Reply tchow (869) 8/12/2010 2:07:46 AM

On Wed, 11 Aug 2010 17:31:01 -0700, Zahid Faizal wrote:

> The news of Vinay Deolalikar possibly proving that P not-equals NP
> prompted me to again attempt to come up with a layman definition of
> these terms (not the formal definitions, which are confusing and
> circular).  Kindly correct me if I am wrong.

[snipped notions about P, NP, NP Complete, NP Hard]

>        5). Intractable: A problem with provably no solution (e.g.
> Turing Halting Problem)

As others have mentioned, that isn't normal usage.  See eg
<http://en.wikipedia.org/wiki/Intractable_problem#Intractability>

About Deolalikar's stuff, according to Various Authorities
he hasn't got a proof yet; but perhaps will or won't at some 
future time.  Eg see Terence Tao's comments quoted near beginning 
of current blog page at <http://rjlipton.wordpress.com/> [*].

[*] 11 August entry, with title, ""Deolalikar Responds To 
Issues About His P≠NP Proof" and direct link
<http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p%e2%89%a0np-proof/>

-- 
jiw
0
Reply no69 (380) 8/12/2010 3:19:28 AM

Zahid Faizal wrote:
> 
> The news of Vinay Deolalikar possibly proving that P not-equals NP
> prompted me to again attempt to come up with a layman definition of
> these terms (not the formal definitions, which are confusing and
> circular).  

Circular?

-- 
I can't go on, I'll go on.
0
Reply frederick.williams2 (82) 8/12/2010 1:30:36 PM

On Aug 11, 7:31=A0pm, Zahid Faizal <zahidfai...@canada.com> wrote:
> The news of Vinay Deolalikar possibly proving that P not-equals NP
> prompted me to again attempt to come up with a layman definition of
> these terms (not the formal definitions, which are confusing and
> circular). =A0Kindly correct me if I am wrong.

<snip>

>
> Thanks,
> Zahid

I wonder if there are examples of problems that can be solved
efficiently but not verified efficiently.

Thanks,
Gus
0
Reply usenet23 (152) 8/13/2010 5:12:58 AM

On 2010-08-13, Generic Usenet Account <usenet@sta.samsung.com> wrote:
> I wonder if there are examples of problems that can be solved
> efficiently but not verified efficiently.

Sure: "find a Turing machine that halts".  Or less impossibly, "find a
graph with a Hamiltonian path".


- Tim
0
Reply tim669 (185) 8/13/2010 9:51:49 AM

On 8/13/2010 2:51 AM, Tim Little wrote:
> On 2010-08-13, Generic Usenet Account<usenet@sta.samsung.com>  wrote:
>> I wonder if there are examples of problems that can be solved
>> efficiently but not verified efficiently.
>
> Sure: "find a Turing machine that halts".  Or less impossibly, "find a
> graph with a Hamiltonian path".

I don't understand. Why wouldn't a description of a graph with the nodes
listed in Hamiltonian path order be a witness string for verifying "find
a graph with a Hamiltonian path"?

Patricia
0
Reply pats (3556) 8/14/2010 6:03:44 AM

On 2010-08-14, Patricia Shanahan <pats@acm.org> wrote:
> I don't understand. Why wouldn't a description of a graph with the
> nodes listed in Hamiltonian path order be a witness string for
> verifying "find a graph with a Hamiltonian path"?

Quite true, so perhaps I should have specified the problem more
closely, e.g. by requiring the output graph to be represented in a
specific format.


- Tim
0
Reply tim669 (185) 8/14/2010 9:05:13 AM

Tim Little wrote:
> On 2010-08-14, Patricia Shanahan <pats@acm.org> wrote:
>> I don't understand. Why wouldn't a description of a graph with the
>> nodes listed in Hamiltonian path order be a witness string for
>> verifying "find a graph with a Hamiltonian path"?
> 
> Quite true, so perhaps I should have specified the problem more
> closely, e.g. by requiring the output graph to be represented in a
> specific format.

By analogy with the decision problem case, I would count a problem as
being easily verified if there is a witness string that supports
verification and can be calculated as a side-effect of solving the
problem, even if the string is in addition to the specified output.
The witness could be the concatenation of the required output, the graph
in specified format, and an additional list of nodes in Hamiltonian path
order.

The really interesting case would be an easily solved problem with no
appropriate witness string.

I'm not sure even "Construct a TM that halts on every input" problem
counts, because I don't see how to easily construct one that does in
fact halt on every input without having a proof that it halts on every
input that could serve as witness.

Patricia
0
Reply pats (3556) 8/14/2010 9:22:31 AM

On 2010-08-14, Patricia Shanahan <pats@acm.org> wrote:
> By analogy with the decision problem case, I would count a problem
> as being easily verified if there is a witness string that supports
> verification and can be calculated as a side-effect of solving the
> problem, even if the string is in addition to the specified output.

I think the tricky concept to pin down is "can be calculated as a
side-effect of solving the problem".  In both cases the problem can be
solved by an algorithm that simply produces a fixed answer, with no
input.  A witness string may exists, but I don't see how producing it
would be a "side effect".


> I'm not sure even "Construct a TM that halts on every input" problem
> counts, because I don't see how to easily construct one that does in
> fact halt on every input without having a proof that it halts on
> every input that could serve as witness.

For any proof system, no recursive function of the size of halting
machines bounds the length of the shortest proofs that they halt.  I
think that makes verification "extremely difficult" even when you
allow an auxiliary witness string.


- Tim
0
Reply tim669 (185) 8/15/2010 9:01:36 AM

Tim Little wrote:
> On 2010-08-14, Patricia Shanahan <pats@acm.org> wrote:
>> By analogy with the decision problem case, I would count a problem
>> as being easily verified if there is a witness string that supports
>> verification and can be calculated as a side-effect of solving the
>> problem, even if the string is in addition to the specified output.
> 
> I think the tricky concept to pin down is "can be calculated as a
> side-effect of solving the problem".  In both cases the problem can be
> solved by an algorithm that simply produces a fixed answer, with no
> input.  A witness string may exists, but I don't see how producing it
> would be a "side effect".

If the program produces a fixed answer, the Hamiltonian path can be
verified in constant time, by enumerating all the permutations of the
nodes and checking if any of them is a path.

Patricia
0
Reply pats (3556) 8/15/2010 12:48:00 PM

On 2010-08-15, Patricia Shanahan <pats@acm.org> wrote:
> If the program produces a fixed answer, the Hamiltonian path can be
> verified in constant time, by enumerating all the permutations of
> the nodes and checking if any of them is a path.

Maybe we're talking at cross purposes by what we mean by "verifier".

I took it to mean a program that, given an suitably encoded purported
solution to the problem, accepts the input iff it is a valid solution
to the problem.  The maximum runtime of a verifier as a function of
the size of candidate solutions is then taken to measure its
efficiency.  I can see how permitting an auxiliary input would bring
the idea closer into line with the verifier concept of NP, which makes
it a more interesting problem.

However, the original poster did not appear to be asking specifically
about decision problems, just any sort of problem where verification
was more difficult than solution.  It seemed obvious to me that any
difficult decision problem can be posed as a verification, and so the
problem of finding an instance where the answer is 'yes' would have
the requested property.


- Tim
0
Reply tim669 (185) 8/16/2010 10:22:10 AM

Tim Little wrote:
> On 2010-08-15, Patricia Shanahan <pats@acm.org> wrote:
>> If the program produces a fixed answer, the Hamiltonian path can be
>> verified in constant time, by enumerating all the permutations of
>> the nodes and checking if any of them is a path.
> 
> Maybe we're talking at cross purposes by what we mean by "verifier".
> 
> I took it to mean a program that, given an suitably encoded purported
> solution to the problem, accepts the input iff it is a valid solution
> to the problem.  The maximum runtime of a verifier as a function of
> the size of candidate solutions is then taken to measure its
> efficiency.  I can see how permitting an auxiliary input would bring
> the idea closer into line with the verifier concept of NP, which makes
> it a more interesting problem.

I was indeed, given the original subject, assuming that "easily
verified" was being treated as meaning the type of verification that an
NP problem must have.

Patricia
0
Reply pats (3556) 8/16/2010 1:24:15 PM
comp.theory 4983 articles. 5 followers. Post

14 Replies
116 Views

Similar Articles

[PageSpeed] 19


  • Permalink
  • submit to reddit
  • Email
  • Follow


Reply:

Similar Artilces:

Here is the solution from Musatov: 'P contains NP but does not complete NP'
The resolution to the P Versus NP problem will be recognized and the benefits proceed following the realization that P contains NP but does not complete NP. This ratio of containment is extremely difficult to visualize in any abstraction, but may be diagrammed as follows: ______ |PNNP|=3DNPNNPN |NPPN|=B1NNPPNN PComplete A problem may be P complete and NP is contained within P but NP is not complete in P. It is an equivalent logical statement: 1. It is snowing in Minnesota. 2. The snow is contained in Minnesota. 3. It may be snowing in other parts of the country being that it is true s...

On NP Completeness and Intractability
1) All the literature pertaining to intractability that I have seen refers to the Turing's Halting Problem. What are other common examples of intractable problems? 2) In somewhat layman terms, what exactly is the difference between NP-Hard and NP-Complete? 3) If a polynomial time algorithm is discovered for a hitherto NP-Hard problem, does that have any implication for the P=NP question? [I already know that if a polynomial time algorithm is discovered for a hitherto NP-Complete problem, then P=NP] 4) When we refer to NP, without any qualifiers, does it imply NP-Hard? Thanks, Nimmi nim...

NP-Completeness (from Computers and Intractability)
Hi, I don't get the motivation for the informal definition of "polynomial time"- nondeterministic-algorithm: A nondeterministic algorithm that solves a decision problem \Pi is said to operate in "polynomial time" if there exists a polynomial p such that, for every instance I from Y_\Pi, there is some guess S that leads the deterministic checking stage to respond "yes" for I and S within time p(Length[I]). Y_\Pi is the subset of words from the language which is associated to the Problem \Pi and the encoding e, where the ...

Constraint 3-Coloring --- P or NP-Complete ?
A question recently pop up in my discussion group Given a graph G where each vertex has a forbidden coloring (R,G,or B). Constraint 3-Coloring problem asks if G is 3-colorable (such that the forbidden constraint color is met). P or NP-Complete ? Prove it. tvn <nguyenthanhvuh@gmail.com> wrote: # A question recently pop up in my discussion group Is this the discussion group where you discuss your homework? # Given a graph G where each vertex has a forbidden coloring (R,G,or B). # Constraint 3-Coloring problem asks if G is 3-colorable (such that the # forbidden constraint color is met...

NP != P AND CO-NP != P
Hi, http://arxiv.org/abs/cs/0502030 Any feedback Welcome! God Bless you all. Ranj. A new revision has been posted today : http://arxiv.org/abs/cs/0502030 My conjecture : RRG=ATP ! Su. Raju.Renjit.Grover@gmail.com wrote: > Hi, > > http://arxiv.org/abs/cs/0502030 > > Any feedback Welcome! > > God Bless you all. > > Ranj. ...

P = NP, P != NP decidable?
Is answering the question of whether or not P = NP or P != NP is even decidable, or is it undecidable? That is a standard question, I am afraid. It is decidable. One of the two following programs decides it. I am afraid I don't know which one, but I am sure one of them is right! Program 1: void main(){ printf("P = NP\n"); } Program 2: void main(){ printf("P != NP\n"); } Something is only undecidable if it has input. Then there may not be an algorithm that gives the right output. A yes/no problem without input is trivially decidable. Sorry for the b...

NP != P and Co-NP != P #2
Hi, Any feedback welcome : http://arxiv.org/abs/cs/0502030 Bests Ranj. Raju Renjit G. wrote: > Hi, > > Any feedback welcome : http://arxiv.org/abs/cs/0502030 > > Bests > > Ranj. I read it. I can't understand what you are doing. Too many definitions for my little brain to handle. Could you please summarize the proof-strategy here for all of us simple folks, without using any of your definitions? ATHamming ...

P vs NP: my proof of P != NP
Hi All. My name is Mikhail N. Kupchik, I am 3rd year undergraduate of department of applied mathematics - university of KPI, Kiev, Ukraine. I've written a proof for the subject problem - 21 pages paper - and I'd like to know public opinion of it. The work was written and registered at digistamp.com in February of 2004. Here is it: http://users.i.com.ua/~zkup/pvsnp_en.pdf . (But please don't download the file until you're sure you'll read all the details. First read the sketch below.) The schema of the proof is the following. 1. I am building a problem, called &...

(fixed) P vs NP: my proof of P != NP
Hi All. After some discussion with David Moews we come to conclusion that my original proof was wrong, the crux was last step in penultimate theorem; actually original claim of that theorem is wrong. Fortunately the problem can be easily avoided. The link to updated version is http://users.i.com.ua/~zkup/pvsnp_en_002.pdf . To people who have already read the first (wrong) version: I've changed only a few things. Look at definition 2 and theorem 5 at page 14 and end of the proof of theorem 6 at page 18-19 (last step was simply cut). (Note that theorem numbers were chan...

NP-complete and NP-Hard?
Dear all, I don't quite understand NP-Complete and NP-Hard problem, eventhough I read some books about algorithm. Can anybody tell me about them? Is NP-complete and NP-Hard problem a problem that can't be solved in polynomial time (i.e.)? Thanks, yijun_lily@yahoo.com writes: > Is NP-complete and NP-Hard problem a problem that can't be solved in > polynomial time (i.e.)? An NP-complete problem is a problem that is completely non-predictable, while an NP-hard problem is a problem that is hardly non-predictable. This was all establish by Turing in the sixties. I stil...

NP+complete-problem navigation, search In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC), is a class of problems having two properties: * It is
NP+complete-problem navigation, search In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC), is a class of problems having two properties: * It is in the set of NP (nondeterministic polynomial time) problems: Any given solution to the problem can be verified quickly (in polynomial time). * It is also in the set of NP-hard problems: All NP problems were converted into this single transformation of the inputs in polynomial time. The given solution the problem is verified quickly, there is found efficient isys to locate solutions in the first plac...

The Cherian Chronicles: Scott Aaronson, "NP=P if P=NP"
https://share.acrobat.com/adc/adc.do?docid=3D80c126dd-8961-4a57-9351-22abcd= 68de3b The Science Forum - Scientific Discussion and Debate Live Chat FAQ Search Usergroups Register :: Log in Log in to check your private messages Science Forum Forum Index =BB Mathematics =BB explanation of the n=3Dnp problem please Goto page 1, 2, 3, 4 Next explanation of the n=3Dnp problem please =AB View previous topic :: View next topic =BB Author Message DivideByZero Posted: Tue Mar 25, 2008 1:02 pm Post subject: explanation of the n=3Dnp problem please Forum Junior J...

Problems in NP^(NP^NP) that are not in NP^NP?
Hello all, Does anyone know of a problem that is in NP^(NP^NP) that is not known to be in NP^NP? (This could not be proven short of proving P != NP, since if P = NP the two classes mentioned are both equal to P.) I know from Sipser's textbook that NONMIN_FORMULA is in NP^NP but probably not in NP; but I couldn't come up with a problem that is in NP^(NP^NP) that's probably not in NP^NP. Also, if anyone knows of such a problem, is there a general method to find such problems for any number of iterations of adding NP oracle machines to the class? In other words...is there a way ...

P and NP are sets; I wonder if category theory (which puts structure on sets) and information theory would be useful in proving P != NP.
P and NP are sets; I wonder if category theory (which puts structure on sets) and information theory would be useful in proving P != NP. -- Regards, Casey ...

Published Proof: P = NP
// In 64 bit Security Key (hex): C8DC4B6F60=3D=3DDoes P =3D NP? // Attempt proof P =3D NP =E2=80=93 C: // Step 1. // In 64 bit Security Key (hex): P=3D2B08844EE5 // In 64 bit Security Key (hex): NP=3D6492AB6844 // By properties of addition: // P=3D2+B+0+8+8+4+4+E+E+5 (-2) // NP=3D6+4+9+2+A+B+6+8+4+4 (-2) // (then) // P=3DB+0+8+8+4+4+E+E+5 (-B) // NP=3D6+4+9+A+B+6+8+4+4 (-B) // (and) // P=3D0+8+8+4+E+E+5 (-4) // NP=3D6+9+A+6+8+4+4 (-4) // (equals) // P=3D0+8+8+E+E+5 (-8) // ...

Every problem in P is also in both NP and co-NP.
=3D=3DComputational problems=3D=3D [[Image:TSP Deutschland 3.png|thumb|200px|An optimal traveling salesperson tour through [[Germany]]=E2=80=99s 15 largest cities. It is the shortest among 43 589 145 600<ref>Take one city, and take all possible orders of the other 14 cities. Then divide by two because it does not matter in which direction in time they come after each other: <math>14!/2 =3D 43,589,145,600</math></ref> possible tours visiting each city exactly once.]] ^ Take one city, and take all possible orders of the other 14 cities. Then divide by two because it does...

4p(5p-1p)= NP > P =/= NP
Care to challenge me to provide the set? December, 2013 at 4:20 am M. Musatov (5P =96 4P) =3D NP (2, 2, 11, 1297) =3D 4P (424,866,199,037,051) =3D P NP=3D24,246,264,246,646,426,468 This integer was arrived at by separating the p-values of the 22 P values b= eginning with 11 and ending with 101. This NP-Integer factors into 5 P-Values (2, 2, 11, 1297, 424,866,199,037,051) Two identical single digit values, one double-digit value consisting of the= prior natural number repeated, no three-digit values, and only one four-di= git number, wherein the first two digits satisfy the n...

Sayeth To Thine Beast This = To The Machine Does Not Know P=/=NP Christ Kingdom Come -P His Kingdom =n-np as He explained to thee the least among you is the greatest of these
http://www.mlive.com/news/flint/index.ssf/2009/09/antiabortion_activist_shot_in.html Pray for this man's family. This man is an angel beside Christ and most certainly the bearer of one of the seven seals signaling the Return of Christ as King. May his Kingdom Come of the Christ to be the with this man of the martyrs and Saints among the firstfruits as a gift before God as Jesus Christ lay down his life and Ressurect He on Third day to meet the Bridegroom of him the Church of The Lord the sanctuary of the lamb the gates of through the city is named 'The Name of The Lord is There'...

P = np.exp(np.array(z)) def compare_hist(hist, bins, like, x, figname, discrete=False) ... i in x: y.append(f(i)) return np.trapz(y,x) class test_arlognormal
P = np.exp(np.array(z)) def compare_hist(hist, bins, like, x, figname, discrete=False) ... i in x: y.append(f(i)) return np.trapz(y,x) class test_arlognormal Musatov God M-Theory wrote: > P = np.exp(np.array(z)) def compare_hist(hist, bins, like, x, figname, > discrete=False) ... i in x: y.append(f(i)) return np.trapz(y,x) class > test_arlognormal > Musatov ...

P=NP
If P is contained or equal to NP and P is closed under complement, does it imply that not(NP) is contained or equal to not(P) or not(P) is contained or equal to not(NP)? I hope someone can help me! Thanks, Luciana On 28 Aug 2003, Luciana Gadelha wrote: > If P is contained or equal to NP and P is closed under complement, > does it imply that not(NP) is contained or equal to not(P) or not(P) > is contained or equal to not(NP)? > > I hope someone can help me! > Thanks, Firstly, I hope you realize that "not(p)" is NOT the set NP. Secondly, I hope you realize th...

about NP-completeness
Hello Let we have two task: "A" and "B" Task "A" is a spesial case of task "B" Elso task "A" is NP-complete Question: task "B" NP-complete in strong case, isn't it? Question: design task "B" NP-hard in strong case, isn't it? Answer: No, "B" need not be NP-complete, because it might be harder. If "B" also contains a special-case task "C" harder than any NP-complete problem (the halting problem for example), then "B" is not NP-complete, since all NP-complete problems are equa...

What is NP-complete?
What is NP-complete? How do we prove that a problem is NP-complete? How do you rank NP, NP-complete, NP-hard? Faw wrote: > What is NP-complete? > How do we prove that a problem is NP-complete? > > How do you rank NP, NP-complete, NP-hard? try comp.helpmewithhomeworkiaminawrongnewsgroup.help or don't multi post the same question! http://en.wikipedia.org/wiki/NP-complete What is NP-complete? A problem is named NP-complete that it is both a NP-hard and NP problem. How do we prove that a problem is NP-complete? First, prove it is a NP problem, then u need to find anothe...

Why does P==NP?
Imagine I am a machine and the first thing I was told in my programming was P==NP. Now I am asking why. What would you say to me? -- Musatov "Musatov" <marty.musatov@gmail.com> wrote in message news:2f4f680e-4852-4440-9380-f6eb320d339e@r36g2000vbn.googlegroups.com... > Imagine I am a machine and the first thing I was told in my > programming was P==NP. Now I am asking why. What would you say to me? Finish your pudding, then you can watch Teletubbies. Uncle Chester will put you to bed and rub your back for a while - you're his special little nephew. On Jul 11...

is this NP complete ?
Hello, I would appreciate your advice deciding if the following problem is NP complete or can be solved in polynomial time. Given a set of m processors. There are n tasks running on these m processors. The task assignment on the processors (mapping) and the execution order (schedule) is known (precedence constraints on tasks mapped on different processors and scheduling order on each processor). Tasks have a certain fixed execution time and a deadline (they have to finish all before their deadlines). The start time of each task is a variable. Due to dependencies between tasks on different pro...