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

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
8/12/2010 12:31:01 AM
comp.theory 5086 articles. 0 followers. marty.musatov (1143) is leader. Post Follow

14 Replies
233 Views

Similar Articles

[PageSpeed] 54
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
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
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
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
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
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
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
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
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
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
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
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
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
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
pats (3556)
8/16/2010 1:24:15 PM
Reply:
Similar Artilces:

US-TX-Austin: .NET Application Architect; VB.NET, ASP.NET, HTML, XML, T-SQL; C-P (45337514411)
US-TX-Austin: .NET Application Architect; VB.NET, ASP.NET, HTML, XML, T-SQL; C-P (45337514411) ============================================================================================== Position: .NET Application Architec Reference: SMC01818 Location: Austin TX Duration: Contract to Perm Skills: Strong writing and verbal communication skills a must. Experience with an internet based startup a plus. Strong experience with estimating development effort based on functional specs also a plus. Minimum 5 years web ...

US-TX-Austin: .NET Application Architect; VB.NET, ASP.NET, HTML, XML, T-SQL; C-P (45334932427)
US-TX-Austin: .NET Application Architect; VB.NET, ASP.NET, HTML, XML, T-SQL; C-P (45334932427) ============================================================================================== Position: .NET Application Architec Reference: SMC01818 Location: Austin TX Duration: Contract to Perm Skills: Strong writing and verbal communication skills a must. Experience with an internet based startup a plus. Strong experience with estimating development effort based on functional specs also a plus. Minimum 5 years web de...

Comprehensive List of OAM&P Standards Bodies
I have an extremely ambitious goal of trying to compile a list of standards bodies that have developed OAM&P standards for network management as well as element management. I am providing the starter. I have listed below standards bodies that have merely provided domain-related information-model/managed-object definitions as well as standards bodies that have given some OAM&P architectural guidelines as well. Kindly augment this list. OAM&P reference architecture (also information model definitions) - IETF/TMN - Telcordia - TINA Consortium - TeleManagement ...

c.l.p.b mini-FAQ
Dear all, As I mentioned earlier, I'm now working abroad, or more correct, abroader ;) and my time here in the UK is very limited. The clpb-miniFAQ needs to be updated, JRS has mentioned some things, TS wants the note about the weekly reog posting to be removed, FreePascal is approaching V2.0, there is a better RTM.EXE/DPMI16BI.OVL and possibly more. I would kindly ask anyone who has anything for the mFAQ to get it to me in the next two weeks, before Friday 15 April. Send it to my normal address the one below _AND PLEASE_ (b)cc: it to robert.a.prins@pqr.ie, where 'pqr' sho...

*.p=` Tons Of Online Games *.p=`
This site has one of the best game rooms online for fun! Visit the arcade room for excitement at http://www.gabbyinc.net!Also has plenty of free games to enjoy! So pass it on... Z?i"L ...

US-AL-Huntsville: SAP Security Admin, SAP R/3 Security, BW Security; C-P (45284457607)
US-AL-Huntsville: SAP Security Admin, SAP R/3 Security, BW Security; C-P (45284457607) ====================================================================================== Position: SAP Security Admin Reference: SMC01136 Location: Huntsville AL Duration: C-P 7+yrs of related experience including detailed knowledge of SAP R/3 Security. Experience with design, development, testing, implementation and on-going maintenance of MIS security systems. SAP R/3 & BW Security Please send your current resume in ...

The Complete Communicator
Looking for an answering/fax package for Win98 that is as good as the proprietary Complete Communicator was [for Win3.1]. "Was" because it seems to have disappeared -- and required its own modem. Everything was excellent: voices, defaults, setup ... Tried downloads/trial versions of others and setup is dreadful/non-intuitive, or worse, freezes system; usual response from help is "modem problem". Looking for basic telephone answering management package! ...

P-P-P-Powerbook
Quite amusing. http://students.uwf.edu/cjg5/sa/thepowerbook.pdf The best part is that even this thing came with a multi-button mouse. 8) Cuss and discuss. -- "The next time you hear an alarming speech about "global warming" on Earth Day, just remember that the first Earth Day featured alarms about the danger of a new ice age." Thomas Sowell ...

US-TX-Austin: WANTED! Logic Design Engineer., Integrated North bridge exp ., P (45353114402)
US-TX-Austin: WANTED! Logic Design Engineer., Integrated North bridge exp ., P (45353114402) ============================================================================================ Position: Microprocessor Logic Designer Reference: SMC01770 Location: Austin TX Duration: Perm Skills: BSEE (MSEE preferred). Integrated Northbridge exp. 5+yrs in logic design and micro architecture development for microprocessors (x86 strongly preferred). Core skills include logic development. Exp in stati...

dediction p-p wave in ECG signal
% to dedction beat-beat by Pan Tompkin Code %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% clear; clc load pvc3.dat; % lOAD THE ECG DATA t=pvc3(:,1); % the first colume is the time3 x=pvc3(:,2); %the second colume is the signal data x=(x-min(x))/(max(x)-min(x)); % normalize between 0-1 N1=length(x); Fs=360; %sampling rate (samling frequncy) fp1 =5; % the low pass frequncy of the band pass filter fs1=5; %the low stop frequncy of the band pass filter fp2=30; % the high pass frequncy of the band pass filter fs2=40; %the high stop frequn...

How to find optimal p and q in ARMA #2
Dear All, I just wonder how to find optimal p and q in ARMA model in Matlab. please the replying..:) thanks you Hafez ...

US-TX-Austin: RF/MMIC Circuit Designer, GaN, GaAs, IP3, 1dB compression, test; P (45328514410)
US-TX-Austin: RF/MMIC Circuit Designer, GaN, GaAs, IP3, 1dB compression, test; P (45328514410) ============================================================================================== Position: RF/MMIC Circuit Designer Reference: SMC01737 Location: Austin TX Duration: Perm Skills: MSEE + 5 years of RF / MMIC circuit design experience in GaN, GaAs, or LDMOS. Device power levels of at least 2 watts and operating frequencies of 900 MHz or higher. Solid working knowledge of associated semiconductor process ...

SRC/P hardware RAID controller drivers
Hi, I've got an E450 with an SRC/P raid controller. Unfortunatly, I don't have the drivers. Can anybody here help me out with this? I think it's the hwraid_2.0 or SUNWhwrd* package. thanks, Dennis -- Don't suffer from insanity... Enjoy every minute of it. ...

US-TX-Austin: Sr. Applications Eng., MCU or DSP board level hw/sw design, C; C-P (45328657604)
US-TX-Austin: Sr. Applications Eng., MCU or DSP board level hw/sw design, C; C-P (45328657604) ============================================================================================== Position: Sr. Applications Eng. Reference: SMC01696 Location: Austin TX Duration: C-P Skills: BSEE plus 2 years hands-on power supply design experience. 2+yrs hands-on MCU or DSP board-level hardware/software design experience. Strong written and verbal communication skills. Proficiency in C language programming. ...

P-code decompiler
Hi All, Wondering if anyone can provide me with a de-compiler for P-coded routines in an MSM / unix environment. I've had a look around the net but not come up with anything. Cheers, Stephen. ...

P+XYd Tons Of Fun P+XYd
This site has one of the best game rooms online for fun! Visit the arcade room for excitement at http://www.gabbyinc.net!Also has plenty of free games to enjoy! So pass it on... Z?i"L ...

Re: how to find P-value ? #3
Another book on this is The Cult of Significance. It's kind of repetitive, but it drives home lots of ways that p-values mess us up. What matters (nearly always) is effect size. I think it was Paul Meehl who said that significance testing answers a question we shouldn't be asking about a thing we shouldn't be interested in. And Jacob Cohen (of power analysis fame) said he thought the best name for the procedure was Statistical Hypothesis Inference Testing (but his wife convinced him not to call it that in their book) and my favorite professor in grad school, Herman Friedman, ...

*++p vs ++*p
Hello, In my understanding, this 2 expressions are equal since '++' operator has a higher precedence than '*' operator. But of course they aren't (I checked with a short test program). So I'm missing something in the C spec about the evalution of expressions. Could anybody give me some hints ? Thanks -- Francis Francis Moreau wrote: > Hello, > > In my understanding, this 2 expressions are equal since '++' operator > has a higher precedence than '*' operator. > > But of course they aren't (I checked with a short test progra...

US-AL-Huntsville: SAP R/3 BASIS ADMIN, 7+yrs exp, SAP rel. 4.6x, UNIX; C-P (45283832410)
US-AL-Huntsville: SAP R/3 BASIS ADMIN, 7+yrs exp, SAP rel. 4.6x, UNIX; C-P (45283832410) ======================================================================================== Position: SAP R/3 BASIS ADMIN Reference: SMC00972 Location: Huntsville AL Duration: C-P Skills: 7 + years hands on exp in SAP R/3 Basis administration. Exp in SAP release 4.6x, Homogenous System Copies, TMS activities, Performance Tuning, Operational Monitoring, UNIX Shell scripting, Documentation, and On_Call support. Special co...

WTB: CP1500 I/O transition card P/N: 370-3926
Our sales rep looking for following items to buy: Sun Part number: 370-3926 Desc: Rear I/O transition card for CP1500. Please contact at wsweeney@gshiis.com. Thank you. Youngjin. ...

p-values #2
Hi, Suppose I have two random variables, X and Y and I do a dependency test (for example: correlation) to check if the random variables are independent or not. That is, my null hypothesis is P_xy = Px * Py and alternate hypothesis is P_xy not = Px * Py. In order to obtain the significance of this method ( p-values), we basically run the same test, that is, calculate the correlation coefficient many times, each time by permuting the sample obtained from Y. If we run it by permuting samples from Y 999 times, then we have the original correlation score and 999 permuted scores. Now, in order to o...

US-TX-Austin: Sr. SoC Design Eng., ASIC design expert, Deep Sub-micron design; P (45326432406)
US-TX-Austin: Sr. SoC Design Eng., ASIC design expert, Deep Sub-micron design; P (45326432406) ============================================================================================== Position: Sr. SoC Design Eng. Reference: SMC01500 Location: Austin TX Duration: Perm Skills: MS in EE or MS in Computer Engineering. 5 to 10 years experience. Must have proven expertise in ASIC design and a firm grasp of all aspects of Deep Sub-micron design flow, including physical design. Scope: ASIC des...

p or ~p
My logic is a little fuzzy. In a legally-inadmissable setting a woman signed 4 letters to me. Because of recency, the last I can identify as 'e'. One I could not verify this morning. The other two were either {'r', 'a'} or {'a', 'r}. Order matters. Has anyone seen a treatment of the word problem with fuzzy logic in c? EC Elijah Cardon posted: > My logic is a little fuzzy. So is your language. > In a legally-inadmissable setting a woman > signed 4 letters to me. Be specific. (1) A letter of the alphabet (2) A letter whi...

p + p
I was using CSS of: p + p {...} ....to indent secondary paragraphs in conversations and descriptive text. This allows not including a class on every secondary <p> tag, of which there are often several for each beginning <p>. I just noticed that while this works fine in FF, it doesn't work at all in IE. Crap! Is there a way to accomplish this that will work in both IE and FF? I know, IE should just get with the program, but I don't think I can wait that long. Regards, Kent Feiler www.KentFeiler.com Scripsit Kent Feiler: ...

case insensitive tab completion in bash?
searched everywhere, haven't found a way to do it. trying to wean myself off tcsh, I used it there (set complete=enhance) all the time. On Wed, 10 Dec 2003 at 05:10 GMT, abuword wrote: > searched everywhere, haven't found a way to do it. > > trying to wean myself off tcsh, I used it there (set complete=enhance) all the time. shopt -s nocaseglob -- Chris F.A. Johnson http://cfaj.freeshell.org =================================================================== My code (if any) in this post is copyright 2003, Chris F.A. Johnson and may...