Re: one sentence proof of 4 Color Mapping Problem; direct method
Chris Heckman wrote:
> I am talking of the NP problem. [...]
There is no "NP problem", just like there is no "Four Theorem".
The problem you're talking about is called "P vs. NP" if you don't want
to bias your viewpoint. If you think they're the same, you call it
"P=NP"; if you think they're different, you call it "P =/= NP".
> I tried to understand NP but was never able to manage it. I did keep
> asking for someone to try to give me an equivalent statement to NP that
> was geometrical. [...]
I'm afraid there isn't one. The "P" refers to how long calculations
take on certain types of machines.
Let's consider the map-coloring problem. Suppose I give you a map with
N countries. One question related to P vs. NP is: How long will it take
for you to determine whether you can color this map with THREE
colorings? (I chose 3 instead of 4 because the 4CT would allow you to
get an answer after 1 calculation; namely, say yes. The 3-coloring
problem, which maps can be colored with 3 colors, is still not
completely solved.)
If you can find a coloring after at most C*N^k calculations, where C
and k are constants (no N's), then the "map 3-coloring problem" (which
is what this problem can be called) is a "P" problem, which means the
number of calculations is at most a polynomial in N.
You may now say that the answer may depend on the calculating machine
you're using. The official standard is what's called a Turing Machine,
and the Church-Turing Thesis says that if you don't like working at
that level, you can use any other "deterministic" program. (No
randomization!)
Now suppose that you have a special type of machine
("non-deterministic"), which allows you to make guesses, but it has a
nice property: If there is a 3-coloring of the map, the guesses will
all turn out correct (!). So an algorithm for this machine would look
like:
(1) Choose a color (red, blue, or green) for Alabama.
(2) Choose a color for Arkansas.
....
(50) Choose a color for Wyoming.
(51) If there are any two states which are adjacent and which have
the same color, output NO and stop.
(52) Otherwise, output YES.
Once again, if there is a 3-coloring of the USA, the non-deterministic
machine will find one and output YES; it will only produce a "bad
coloring" if there are no 3-colorings whatsoever.
Now, if a non-deterministic machine can solve the problem of "map
3-coloring" with at most C*N^k calculations (again, with C and k
constants), then "map 3-coloring" is said to be an "NP" problem, short
for "Nondeterministic Polynomial". You can adapt the program above for
a general map, and the running time will be at most a constant times
N^2, so "map 3-coloring" is an NP problem. (You may also hear that "map
3-coloring" "is in NP". Same thing.)
Now, every P problem is an NP problem. The proof is to take the
algorithm that shows that your problem is in P, and just run it on the
non-deterministic machine. (The ND machine doesn't have to use
non-determinism!)
The big question --- P vs. NP --- is whether every NP problem is a P
problem. You sometimes hear about "NP complete problems"; these are
problems which are basically the most difficult of the NP problems. If
ANY of these problems is in P, then ALL NP problems are in P.
For general problems, N will represent "the size of the problem", and
this is more complicated for some problems. There are several websites
which list some problems known to be NP-complete, including the
following. A lot of problems in Graph Theory are known to be
NP-complete. (The Travelling Salesman Problem is one of the most famous
NP-complete problems.)
http://en.wikipedia.org/wiki/NP-Complete#Example_problems
http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html (88
are listed here, although the topics are discussed in a technical
manner.)
A recent paper states that the Sudoku problem (is there a solution to a
partially-filled in Sudoku grid?), when generalized to an (n^2) by
(n^2) grid, is also NP-complete.
--- Christopher Heckman
a_pluton...@xxxxxxxxxxx wrote:
> [...]
> I ask myself what would be a Reductio ad Absurdum RAA steps for [the P vs. NP]
> problem? The implication step using RAA. Seems to me that P and NP are
> connected so that if I suppose false for the conjecture there is no way
> of writing out its implication.
It depends on which result you want to prove, whether P is NP or not.
(See my previous post for a description of P and NP.)
If you want to prove P is not NP, using RAA, then you assume it is.
That means that if you choose any NP-complete problem, there is a
polynomial-time algorithm which solves it. You can either show that
this algorithm either does not work, or that it doesn't take time at
most C*N^k, contradicting the assumption that there _was_ a
polynomial-time algorithm.
If you want to prove P is NP, using RAA, you assume that P and NP are
different, so there is an NP-complete problem which cannot be solved in
polynomial time. To get a contradiction to this, you would basically
have to construct an algorithm (procedure) which solves the NP-complete
problem, and does it with at most C*N^k steps. But you're basically
building the algorithm in P to solve the NP-complete problems, so you
may as well just present the algorithm in a direct proof.
--- Christopher Heckman
A.P. writes:
Usually I read only parts of your post, but since I know so little
about P=NP
I read it several times looking for some clues.
The reason I took on this problem in 1996 or thereabouts was because I
did not want to ever miss any opportunity to use the new idea that
Natural Numbers are Infinite Integers and not finite integers.
Could we say that if Natural Numbers are Adics and since Adics are
equinumerous to Reals favors P= NP.
But, now, if Natural Numbers (the basis for counting machines) are
finite-integers then they have a different cardinality from Reals and
hence favoring P=/=NP result.
I am not so sure that there is no geometrical equivalency to P=NP.
Perhaps the equivalency is the idea that Eucl geom is what is
geometrically-equinumerous to Loba geom where we define
geometrically-equinumerous as the property of being open and not closed
and where Riem geom is closed.
So that whenever a situation arises when it turns out that P=NP is
because the situation is geometrically Euclid geom versus Loba geom.
And when a situation arises where P=/=NP is when Riem geom versus
either Eucl or Loba geom is involved.
Archimedes Plutonium
www.iw.net/~a_plutonium
whole entire Universe is just one big atom
where dots of the electron-dot-cloud are galaxies
.
Relevant Pages
- Re: A dungeon generator
... rooms will not fit in the map, so your algorithm will fail. ... each level has 16 possible starting templates. ...
(rec.games.roguelike.development) - Re: A dungeon generator
... then it automatically turns in the former kind of algorithm. ... If it fails to generate a map ... rooms, then after a hundred more fails, five rooms, etc. ... each level has 16 possible starting templates. ...
(rec.games.roguelike.development) - A Random Town Generation Algorithm
... I have implemented a random town generation algorithm algorithm. ... Pick a random point close to the centre of the map. ... And do the same for each of the new rectangles created by this until you've reached a minimum size. ... Ideally all these new created subdivisions should be stored in some list. ...
(rec.games.roguelike.development) - Re: Precise Permissive Field of View: Request for comments
... that convinced me to use it as a default FOV algorithm in RoguelikeLib:) ... The interface is not yet very swapable, I will work on it with a new version. ... map data structure, it should have a map interface (not necessarily ...
(rec.games.roguelike.development) - Re: What big scientific changes will ...
... poliaminal time, a non poliaminal algo is no solution for me. ... NP-complete problems are not as hard as they seem. ... If such an algorithm existed, ... algorithm exists and in 1882 this was proven by von Lindemann. ...
(sci.math) |
|
