f



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 5122 articles. 0 followers. marty.musatov (1143) is leader. Post Follow

14 Replies
537 Views

Similar Articles

[PageSpeed] 33

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: