P=NP Explained So We Can All Tackle It
Charlie-Boo
the P=NP problem requiring only high school math to understand so
everyone can tackle it?
From the little that I have checked out, it seems to be a combination
of simple Theory of Computation (recursive and r.e. sets) and
combinatorial analysis - number of steps needed due to the number of
possible inputs and outputs. But we would all benefit from an as
simple as possible explanation.
C-B
Joshua Cranmer
> Can anybody give a simple as possible self-contained explanation of
> the P=NP problem requiring only high school math to understand so
> everyone can tackle it?
Before I start, I want to point out that P versus NP deals specifically
with decision problems, not functional problems. So the version of, say,
TSP that is in NP is not "find the shortest-length Hamiltonian tour" but
"does there exist a Hamiltonian tour of at most p?" (it's something that
I've generally seen glossed over in informal discussion.
The set of problems P are those (decision) problems that we can find an
answer for in polynomial time with respect to the size of the input. For
example, I can write an algorithm to see if a given element is in a
sorted array that will take O(lg n) time, so that problem is in P.
The set of problems NP are those (decision) problems that can be
verified in polynomial time, again with respect to the size of the
input. For example, if you gave me the shortest-length Hamiltonian tour
of a graph, I can tell you whether or not a Hamiltonian tour of at most
p weight exists in that graph, so that problem is in NP. We do not yet
know, however, if this problem is in P.
It should be clear that every problem in P is in NP, so P is at least a
subset of NP. The question is whether or not the two sets of problems
are equivalent--that is, if we can verify a problem in polynomial time,
can we solve it in polynomial time? That is the essence of P = NP.
With that said, there is one more helpful information to solving the
issue. To prove the affirmative, one has to show that all problems in NP
has a polynomial time solution. The class NP-complete is a set of
problems to which every problem in NP can be reduced (in polynomial
time). If one can find a polynomial time algorithm for one of these
problems, that suffices to prove the affirmative (or to prove a problem
known to be in P is also in NP-complete).
That is probably as simple an explanation as could be given, but that
doesn't imply that lay people would be able to solve it easily. If, as
is widely believed, P != NP, than the tools to prove it so are beyond
simple, lay introductions.
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
Daniel A. Jimenez
Charlie-Boo <shyma...@gmail.com> wrote:
>Can anybody give a simple as possible self-contained explanation of
>the P=NP problem requiring only high school math to understand so
>everyone can tackle it?
Here's my attempt to make it as simple as possible without losing too
much precision:
Let L be a set of Java strings. Let f be a Java method like this:
boolean f (string s, string c);
that returns returns "true" if s is in L, or "false" otherwise.
The amount of time taken by f is limited by another method:
float p (string s, string c, int K) {
return Math.pow (s.length() + c.length(), K);
}
where K is a constant.
The question of whether P = NP is this:
For every set L for which a method f(s,c) answers the question "is s in
L," in an amount of time at most p(s,c,K), is there another method:
boolean f2 (string s);
taking an amount of time at most p(s,"",K2) that can answer the same
question?
That theoretically should not blow the mind of a C student in a freshman
CS class. I'm leaving out some stuff, like the fact that L is infinite,
and s and c should be efficient encodings.
P is for "polynomial" because p(s,c,K) is a polynomial in the size of the
strings. NP is for "non-deterministic polynomial" because if we could
"guess" a right value of c we could answer the question about whether
s is in L with just one fast call to f.
For example, suppose L is the set of string encodings of all logic
circuits for which some combination of inputs yields the output "true."
Then the c in f(s,c) could be an encoding of a combination of inputs
that makes the circuit "true," and f could be computed in time at most
p(s,c,K) by just verifying that c makes the circuit output "true."
But without some c, is there an f2(s) that could decide the question in
time at most p(s,"",K2), even if we let K2 > K? Nobody knows the
answer to that question.
--
Daniel Jimenez djim...@cs.utexas.edu
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
" " -- John Cage
jbriggs444
P is a class of problems.
NP is a class of problems.
Each problem is itself a set of questions. Each question has a yes or
no answer.
The size of a question is simply its length when encoded as input to a
computer (or computer program).
A program is said to solve a problem when it can correctly answer
every question that comprises that problem.
A program is said to solve a problem "in polynomial time" when there
is a fixed polynomial function p such that for every question size s,
the program can correctly every question of that size in no more than p
(s) steps. [There's a helpful result available here -- if you can
answer "yes" in computable bounded time when the correct answer is
"yes", it follows that you can set up a watchdog timer and answer "no"
in bounded time as well]
P is the class of problems that can be solved in polynomial time by
some Turing machine.
NP is the class of problems that can be solved in polynomial time by
some non-deterministic Turing machine.
[Note that the distinction between a Turing Machine and a program
running on a [Universal] Turing Machine is pretty much irrelevant.
And since most ordinary programming languages are Turing complete if
you idealize them to allow unlimited dynamic memory, it doesn't matter
whether you think in terms of Turing machines or programs written in C+
+, Java or your own language of choice]
I assume that you know what a Turing machine is or can google for it.
A non-deterministic Turing machine is one that does not always follow
a single pre-determined path of execution.
For instance, instead of:
10 GOTO 100
A non-deterministic machine can have behavior like
10 GOTO 100 or GOTO 200
One way of looking at things is that a non-deterministic machine
pursues multiple execution paths at the same time, each with
independent storage. In fact, it can pursue arbitrarily many such
paths. [From this point of view, a non-deterministic machine achieves
power through massive parallelism]
If any of these execution paths halts, that path (and any output that
it generated) is taken as the result of executing the program. Any
paths that fail to halt are generally ignored.
Let me hand wave past the question of what happens when two or more
paths halt and return different answers. As I recall, it's the
programmer's responsibility to avoid that situation if he wants his
program to achieve a well-defined result.
I was taught this formalism over 30 years ago. Other people on Usenet
will use a lot of informality when speaking of non-deterministic
Turing machines and talk about machines that "always guess right",
which are equipped with a random oracle or which magically come up
with a result and only need to check it. The various presentations
are typically compatible. We're all talking about the same thing in
different ways.
Daniel A. Jimenez
jbriggs444 <jbrig...@gmail.com> wrote:
> [some stuff deleted]
>If any of these execution paths halts, that path (and any output that
>it generated) is taken as the result of executing the program. Any
>paths that fail to halt are generally ignored.
>
>Let me hand wave past the question of what happens when two or more
>paths halt and return different answers. As I recall, it's the
>programmer's responsibility to avoid that situation if he wants his
>program to achieve a well-defined result.
>
>I was taught this formalism over 30 years ago. Other people on Usenet
>will use a lot of informality when speaking of non-deterministic
>Turing machines and talk about machines that "always guess right",
>which are equipped with a random oracle or which magically come up
>with a result and only need to check it. The various presentations
>are typically compatible. We're all talking about the same thing in
>different ways.
Both approaches can be formal or informal. See:
http://groups.google.com/group/comp.theory/browse_thread/thread/ad407db8b868cee7/4e6300c618cd93c8
for a discussion of the disadvantages to the multiple-execution-paths
version of NP. Basically, it can confuse newbies: lots of multiple
execution paths sounds a lot like an exponential number of threads,
which is more powerful than NP.
none
> The class NP-complete is a set of problems to which every problem in NP
> can be reduced (in polynomial time).
Does this mean that the sets NP and NP-complete are the same sets? If not,
what's an example of a problem that's NP but not NP-complete?
> If one can find a polynomial time algorithm for one of these problems,
> that suffices to prove the affirmative (or to prove a problem known to
> be in P is also in NP-complete).
So, solving just one NP-complete problem in polynomial time effectively
solves them all in polynomial time?
Robert Israel
> Joshua Cranmer wrote:
>
> > The class NP-complete is a set of problems to which every problem in NP
> > can be reduced (in polynomial time).
>
> Does this mean that the sets NP and NP-complete are the same sets? If not,
> what's an example of a problem that's NP but not NP-complete?
No, if P is not NP they are not the same. Any problem in P is in NP, but
(if P is not NP) it is not NP-complete.
> > If one can find a polynomial time algorithm for one of these problems,
> > that suffices to prove the affirmative (or to prove a problem known to
> > be in P is also in NP-complete).
>
> So, solving just one NP-complete problem in polynomial time effectively
> solves them all in polynomial time?
Yes.
--
Robert Israel isr...@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada