I would not for a minute say the two are comparable but for your understanding, the risk of getting AIDS from unprotected vaginal intercourse are 1 in 5,000,000 and you don't hear of many people doing that outside a committed relationship, do you ?
In terms of expensive life altering events, I'd wager that unprotected vaginal intercourse comes with a somewhat greater risk of getting KIDS. It's a good thing all of those are born to parents in committed relationships - otherwise your analogy might argue that quite a few people risk life altering events without thinking too hard about it at all.
(I have heard that professional musicians can tell if it's 440 or 442 khz, but I screw 'em - my guitar works fine for me 99% of the time)
Speaking as a fellow amateur, I'm afraid your shredding megahertz thrash solos will mostly be inaudible to me, but I'm sure the beluga whales will be ecstatic about your power chords if you drop the tuning just a little...
The class of P-complete problems is widely held to be inherently sequential.
Proving P-completeness amounts to proving that your problem is sequentially solvable in polynomial time (membership in class P), and proving that it can be reduced to another P-complete problem in polylogarithmic time on a parallel machine. Thus, you can establish that it is at least as hard to parallelize as the other P-complete problems.
There is, to my knowledge, no formal proof that P-complete problems can't be solved efficiently in parallel, but if an efficient parallel algorithm were to emerge, a lot of researchers would be very surprised indeed.
Actually I *did* recall correctly, but as it turns out, my complexity theory courses and books predate the primes-is-in-P proof, so I'll update my view of the relationship of the complexity classes. Thanks for the heads-up!
Also, I'm apparently guilty of having confused the factorization problem with the complement of the primes problem. Mea culpa. I'll maintain that primes is polynomially equivalent to co-primes, though. =)
If anyone needs me, I'll be over in the corner revising my view of the world.
While I agree with what you say, I just feel compelled to add a little something:
> To give you an example, many programmers > encrypt things. Many of them are not aware, while > doing so, that the whole private key/public key > system is based upon the characteristics of NP-hard > problems.
I assume you are referring to the difficulties involved in factoring large numbers. While that problem (deciding composites) is a tough one, I don't think it has been proven to be NP-hard.
IIRC, it's a bit of an odd one by being polynomial-time reducible to its complement problem of deciding primes. Since these are both members of NP, an NP-hardness proof for either problem would mean that both are in NPC and coNPC, which would prove identity between NP and coNP.
While that would be nice, I think it would be a tad optimistic to assume it is possible. Try to reduce an NPC problem to primes, you'll see what I mean.
Right you are; I forgot to include the comefrom construct and its equivalents in the vice-versa. Let us split this humble-pie, and I'll scurry out of view before this spirals any further from the topic.
> There's a certain number of minimum features a > language must support before its considered turing > complete. (These usually include things like variable > assignments, if statements, and loops.)
Pardon, but I can no longer contain my pedantry... I trust to be forgiven, since there is a fairly precise definition of the term you are bandying about.
It is pointless to "consider" something Turing complete, as it is not a matter of opinion. One either proves the completeness of a language, disproves it, or mumble "I really have no idea". Also, Turing completeness is not a vague checklist of language features, it is the quite unambiguous property that a language is capable of expressing a simulator for an arbitrary Turing machine.
If you have loops you don't need "if", by the way. And vice versa.
Slashdot Mirror
I would not for a minute say the two are comparable but for your understanding, the risk of getting AIDS from unprotected vaginal intercourse are 1 in 5,000,000 and you don't hear of many people doing that outside a committed relationship, do you ?
In terms of expensive life altering events, I'd wager that unprotected vaginal intercourse comes with a somewhat greater risk of getting KIDS. It's a good thing all of those are born to parents in committed relationships - otherwise your analogy might argue that quite a few people risk life altering events without thinking too hard about it at all.
(I have heard that professional musicians can tell if it's 440 or 442 khz, but I screw 'em - my guitar works fine for me 99% of the time)
Speaking as a fellow amateur, I'm afraid your shredding megahertz thrash solos will mostly be inaudible to me, but I'm sure the beluga whales will be ecstatic about your power chords if you drop the tuning just a little...
It has been attempted, but with modest success...
The class of P-complete problems is widely held to be inherently sequential.
Proving P-completeness amounts to proving that your problem is sequentially solvable in polynomial time (membership in class P), and proving that it can be reduced to another P-complete problem in polylogarithmic time on a parallel machine. Thus, you can establish that it is at least as hard to parallelize as the other P-complete problems.
There is, to my knowledge, no formal proof that P-complete problems can't be solved efficiently in parallel, but if an efficient parallel algorithm were to emerge, a lot of researchers would be very surprised indeed.
> why is parallel "embarassing"? oh I see, facts aren't good for your bottom line.
Actually that is a common expression, and not something he pulled out of his heinie - peek here
Well, this was certainly interesting...
Actually I *did* recall correctly, but as it turns out, my complexity theory courses and books predate the primes-is-in-P proof, so I'll update my view of the relationship of the complexity classes. Thanks for the heads-up!
Also, I'm apparently guilty of having confused the factorization problem with the complement of the primes problem. Mea culpa. I'll maintain that primes is polynomially equivalent to co-primes, though. =)
If anyone needs me, I'll be over in the corner revising my view of the world.
While I agree with what you say, I just feel compelled to add a little something:
> To give you an example, many programmers
> encrypt things. Many of them are not aware, while
> doing so, that the whole private key/public key
> system is based upon the characteristics of NP-hard
> problems.
I assume you are referring to the difficulties involved in factoring large numbers. While that problem (deciding composites) is a tough one, I don't think it has been proven to be NP-hard.
IIRC, it's a bit of an odd one by being polynomial-time reducible to its complement problem of deciding primes. Since these are both members of NP, an NP-hardness proof for either problem would mean that both are in NPC and coNPC, which would prove identity between NP and coNP.
While that would be nice, I think it would be a tad optimistic to assume it is possible. Try to reduce an NPC problem to primes, you'll see what I mean.
Right you are; I forgot to include the comefrom construct and its equivalents in the vice-versa.
Let us split this humble-pie, and I'll scurry out of view before this spirals any further from the topic.
> There's a certain number of minimum features a
> language must support before its considered turing
> complete. (These usually include things like variable
> assignments, if statements, and loops.)
Pardon, but I can no longer contain my pedantry... I trust to be forgiven, since there is a fairly precise definition of the term you are bandying about.
It is pointless to "consider" something Turing complete, as it is not a matter of opinion. One either proves the completeness of a language, disproves it, or mumble "I really have no idea". Also, Turing completeness is not a vague checklist of language features, it is the quite unambiguous property that a language is capable of expressing a simulator for an arbitrary Turing machine.
If you have loops you don't need "if", by the way. And vice versa.