
P, NP, NP Complete, Intractable in layman terms?
The news of Vinay Deolalikar possibly proving that P notequals 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/explainerpnp.html
2). http://cacm.acm.org/magazines/2009/9/38904thestatusofthepversusnpproblem/fulltext
3). http://www.aolnews.com/surgedesk/article/pnpwtfashortguidetounderstandingvinaydeolalikarsmat/19586401
4). http://mathworld.wolfram.com/NPHardProblem.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 notequals 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 notequals 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 NPcomplete) are classes of only decision
problemsthose 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.
NPcomplete 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 NPcomplete problems (or NPhard 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.
NPhard is a generalization of NPcomplete. Unlike the other three
mentioned classes, NPhard includes nondecision problems. Roughly
speaking, a problem is NPhard if you can use it to solve an NPcomplete
problem. An example: the boolean satisfiability problem asks if there
exists an assignment for variables that satisfies a given equation; this
problem is NPcomplete. A related problem is to, given such an equation,
find an assignment (if it exists) that would satisfy the equation. This
one is NPhard: 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
quicklynot 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 <9dcc8a5dc1de48d0bf8c62e86e8f0047@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 NPhard problem is in NP then it is NPcomplete."
> 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 tchowatalumdotmitdotedu
The range of our projectileseven ... the artilleryhowever 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 notequals 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/deolalikarrespondstoissuesabouthisp%e2%89%a0npproof/>

jiw


0




Reply

no69 (380)

8/12/2010 3:19:28 AM


Zahid Faizal wrote:
>
> The news of Vinay Deolalikar possibly proving that P notequals 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 notequals 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 20100813, 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 20100813, 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 20100814, 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 20100814, 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 sideeffect 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 20100814, 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 sideeffect 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
sideeffect 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 20100814, 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 sideeffect 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
> sideeffect 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 20100815, 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 20100815, 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



14 Replies
195 Views
Similar Articles
[PageSpeed]
59

Similar Artilces:
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 ... NP != P AND CONP != PHi,
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 CoNP != P #2Hi,
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
proofstrategy 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 &... 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... (fixed) P vs NP: my proof of P != NPHi 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 1819 (last step was
simply cut). (Note that theorem numbers were chan... NPcomplete and NPHard?Dear all,
I don't quite understand NPComplete and NPHard problem, eventhough I
read some books about algorithm. Can anybody tell me about them?
Is NPcomplete and NPHard problem a problem that can't be solved in
polynomial time (i.e.)?
Thanks,
yijun_lily@yahoo.com writes:
> Is NPcomplete and NPHard problem a problem that can't be solved in
> polynomial time (i.e.)?
An NPcomplete problem is a problem that is completely
nonpredictable, while an NPhard problem is a problem that is hardly
nonpredictable. This was all establish by Turing in the sixties.
I stil... NP+completeproblem navigation, search In computational complexity theory, the complexity class NPcomplete (abbreviated NPC or NPC), is a class of problems having two properties: * It isNP+completeproblem
navigation, search
In computational complexity theory, the complexity class NPcomplete
(abbreviated NPC 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 NPhard 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=3D80c126dd89614a57935122abcd=
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... On NP Completeness and Intractability1) 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
NPHard and NPComplete?
3) If a polynomial time algorithm is discovered for a hitherto NPHard
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 NPComplete problem, then P=NP]
4) When we refer to NP, without any qualifiers, does it imply NPHard?
Thanks,
Nimmi
nim... 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)
// ... NP and CoNPMy question is, why can't an NTM use an NTM deciding the complement
language in deciding its language. Let me describe, for example, an
NTM for NSAT ... a Multitape NTM that simulates the NTM for SAT with
the following changes:
1) Take the "yes" halting state for the NTM for SAT
and add states so that this new NTM writes "YES" on the second tape,
then halt.
2) Read the second tape, if it says "YES" halt in the "NO" state,
otherwise halt in the "YES" state.
I have heard people say that this is "cheating" because we cannot
c... Every problem in P is also in both NP and coNP.=3D=3DComputational problems=3D=3D
[[Image:TSP Deutschland 3.pngthumb200pxAn 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... NPCompleteness (from Computers and Intractability)Hi, I don't get the motivation for the
informal definition of "polynomial time"
nondeterministicalgorithm:
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 ... 4p(5p1p)= NP > P =/= NPCare 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 pvalues of the 22 P values b=
eginning with 11 and ending with 101.
This NPInteger factors into 5 PValues
(2, 2, 11, 1297, 424,866,199,037,051)
Two identical single digit values, one doubledigit value consisting of the=
prior natural number repeated, no threedigit values, and only one fourdi=
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 =nnp as He explained to thee the least among you is the greatest of thesehttp://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_arlognormalP = 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
MTheory 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
... Constraint 3Coloring  P or NPComplete ?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 3Coloring problem asks if G is 3colorable (such that the
forbidden constraint color is met). P or NPComplete ? 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 3Coloring problem asks if G is 3colorable (such that the
# forbidden constraint color is met... are there semidecidable problems that are neither NP, nor NPhard, nor coNP?Hi People,
Let U be the union of classes NP, NPhard and coNP.
What is the complement of U?
Is there any problem A such that A is semidecidable and A is not in
NP and A is not NPhard?
Thanks in advance.
Best regards,
Daniel
... P=NPIf 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 NPcompletenessHello
Let we have two task: "A" and "B"
Task "A" is a spesial case of task "B"
Elso task "A" is NPcomplete
Question: task "B" NPcomplete in strong case, isn't it?
Question: design task "B" NPhard in strong case, isn't it?
Answer: No, "B" need not be NPcomplete, because it might be harder. If
"B" also contains a specialcase task "C" harder than any NPcomplete
problem (the halting problem for example), then "B" is not NPcomplete,
since all NPcomplete problems are equa... What is NPcomplete?What is NPcomplete?
How do we prove that a problem is NPcomplete?
How do you rank NP, NPcomplete, NPhard?
Faw wrote:
> What is NPcomplete?
> How do we prove that a problem is NPcomplete?
>
> How do you rank NP, NPcomplete, NPhard?
try comp.helpmewithhomeworkiaminawrongnewsgroup.help
or don't multi post the same question!
http://en.wikipedia.org/wiki/NPcomplete
What is NPcomplete?
A problem is named NPcomplete that it is both a NPhard and NP problem.
How do we prove that a problem is NPcomplete?
First, prove it is a NP problem, then u need to find anothe...



