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

[Zahid Faizal]

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

[Francesco S. Carta]

Post by Zahid Faizal
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.

[Joshua Cranmer]

Post by Zahid Faizal
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).

Post by Zahid Faizal
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.

Post by Zahid Faizal
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.

Post by Zahid Faizal
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.

[t***@lsa.umich.edu]

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

Post by Zahid Faizal
1). P: A problem that can be solved efficiently

Reasonable.

Post by Zahid Faizal
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."

Post by Zahid Faizal
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."

Post by Zahid Faizal
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."

Post by Zahid Faizal
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."

[James Waldby]

Post by Zahid Faizal
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]

Post by Zahid Faizal
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/>

[Frederick Williams]

Post by Zahid Faizal
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?

[Generic Usenet Account]

Post by Zahid Faizal
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.

<snip>

Post by Zahid Faizal
Thanks,
Zahid

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

Thanks,
Gus

[Tim Little]

Post by Generic Usenet Account
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

[Patricia Shanahan]

Post by Tim Little

Post by Generic Usenet Account
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

[Tim Little]

Post by Patricia Shanahan
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

[Patricia Shanahan]

Post by Tim Little

Post by Patricia Shanahan
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

[Tim Little]

Post by Patricia Shanahan
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".

Post by Patricia Shanahan
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

[Patricia Shanahan]

Post by Tim Little

Post by Patricia Shanahan
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

[Tim Little]

Post by Patricia Shanahan
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

[Patricia Shanahan]

Post by Tim Little

Post by Patricia Shanahan
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