Re: P is not equal to NP (and this is why)


Proginoskes wrote:
matt.zellman@xxxxxxxxx wrote:
I really need to start using more provocative subject lines. Anyway,
this is a proof that 3CP cannot be in P.

I, for one, am swamped. Classes began last week here at Arizona State,
and there's too much administrative stuff to do to look at anything in
depth. Maybe I can look at it in a few weeks.


Oh, I definitely understand. I posted it here when I did to get it out
before I start classes myself.

You should be following another thread, "SAT is in P, CLIQUE is in P",
also in sci.math:
http://groups.google.com/group/sci.math/browse_frm/thread/0b31f092626067b3/df0c74924522fa96#df0c74924522fa96

(I put the ">" before the link so that Google Groups doesn't split the
link across the line.)

--- Christopher Heckman


Yes indeedy. The algorithm is interesting, but the approach fails
totally for a couple interesting classes of graphs.

matt.zellman@xxxxxxxxx wrote:
so a couple of weeks ago, I posted here asking for help with a paper. I
decided to go ahead and put what I have out here so people can look it
over. I'll reiterate some of the concepts I went over in the previous
thread, and then see if my reasoning is sound.

1. k-chromatic Edge Replacement Subgraphs (^kERSs)

a ^kERS is a k-chromatic graph that contains at least one pair of
nonadjacent vertices for which no valid k-colorings exist when they are
colored the same color. The ^kERS as a whole functions in exactly the
same way as a single edge, and a k-chromatic graph can be transformed
G=>G' by replacing an edge with a ^kERS, a process I have called
"expansion by edge-replacement."

The reverse process, replacing a ^kERS with an edge, I have termed
"reduction by edge-replacement."

2. Boundary Points

Every graph has at least one set of vertices (of a size greater than or
equal to the chromatic number k of the graph) for which no valid
k-colorings exist when the vertices in the set are colored with less
than k colors. Any such set of vertices is a set of "boundary points."

3. Basic k-chromatic Graphs

A primary basic k-chromatic graph is constructed by taking a basic
(k-1)-chromatic graph and adding one vertex, which is then connected to
an entire set of boundary points with edges or ^kERSs. A secondary
basic k-chromatic graph is an expansion of a primary basic k-chromatic
graph by edge-replacement. The basic 1-chromatic graph is a single
vertex.

Every graph with chromatic number k contains at least one basic
k-chromatic graph as a subgraph, and no basic (k+1) chromatic graphs as
subgraphs.



The scope of the three-color problem is bounded only by the size of the
graph. That is, consider the graph below (Figure A):

O---O---O---O---O
/|\ / \ / \ / \ /|
O-O O O O O |
\|/ \ / \ / \ / \|
O---O---O---O---O

This graph is 4-chromatic, as are all the graphs with the same end
regions and different lengths of the same pattern in the middle. I
could change something anywhere on the graph to make the chromatic
number 3. For example, I could delete the leftmost vertex, I could add
a vertex in the middle of the edge at the right end, or I could change
any of the middle vertices to other configurations.

To put it succinctly, in order to determine the colorability of the
graph, I am required to make an exhaustive analysis. No local analysis
would guarantee that I find all the structures that determine the
colorability of the graph.



Suppose, however, that using edge-replacement, we could reduce the
graph to some configuration that could be analyzed locally. If we
replace all the ^3ERSs with edges until there are no ^3ERSs left, we
will be left with a graph that can be analyzed locally, in
deterministic polynomial time. We simply have to go through the graph,
and for each vertex, we look for all the edges connected to that
vertex, and take note of which vertex is on the other end of each edge.
Then we look for all the edges between those vertices, and build a
subgraph from them. We can try to color this subgraph with two colors.
If we can, then the graph may still be 3-colorable. If we can't, then
the graph is not 3-colorable.

It certainly seems like a reasonable course of action, but it turns out
that even identifying ^3ERSs in a graph is necessarily exponential over
the inputs. Go back to the example graph shown above. If we take it
back to the basic 3-chromatic graph it is constructed from, we are left
with the graph below (Figure B):

O---O---O---O---O
/ \ / \ / \ / \ /|
O O O O O |
\ / \ / \ / \ / \|
O---O---O---O---O

It is an example of a graph in which a single ^3ERS has been iterated 4
times from a simple triangle. The ^3ERS by itself looks like this
(Figure C):

1@---O2
\ /|
3O |
/ \|
4@---O5

(where the @s signify the endpoints of the edge that is being replaced,
and the vertices are numbered from 1-5 to help us out later)

In each even iteration of this ^3ERS, an edge can be constructed
between the initial vertex 1, and vertex 5 of the
second/fourth/sixth... iteration, without changing the colorability of
the graph. Alternatively, an edge can be constructed between the
initial vertex 4 and vertex 2 of that iteration. For odd iterations,
they switch: initial vertex 1 can be connected to vertex 2 of the
third/fifth/seventh... iteration, or initial vertex 4 can be connected
to vertex 5 of that iteration.

Suppose that for each iteration, we construct one of these two edges.
Such a construction across iterations creates a ^3ERS that cannot be
reduced to another ^3ERS, but only straight to an edge. Each iteration
adds 3 vertices and 7 edges to the graph. The extra edge we add makes
it 3 and 8. We can represent which edge we have constructed at each
iteration by simply making an ordered list: 14411144444... This
particular example is equivalent to the graph represented by
41144411111, but not to the graph represented by 11411144444 or any
other graph in the set. There are therefore at least 2^(i-2) unique
possible ^3ERSs for each iteration i (i>1). Relating this to the size
of the input (suppose our input is just the list of edges), the number
of necessary tests for unique ^3ERSs for a graph with E edges must
necessarily exceed (since our starting set of ^3ERSs is severely
limited, as are the rules for construction):

2^(E/8-2) for E>16


Since without edge-replacement, the scope of the problem is unbounded,
and therefore requires an exhaustive search, and with edge replacement,
it requires a number of tests that is at least exponential over the
size of the input, we are forced to conclude that the 3-coloring
problem cannot be solved deterministically in polynomial time.

And, as a direct result, P is not equal to NP.


Is there anything I've missed?

.

Relevant Pages

  • a proof for consideration
    ... same way as a single edge, and a k-chromatic graph can be transformed ... In each even iteration of this ^3ERS, ... Such a construction across iterations creates a ^3ERS that cannot be ...
    (sci.math)
  • P is not equal to NP (and this is why)
    ... same way as a single edge, and a k-chromatic graph can be transformed ... In each even iteration of this ^3ERS, ... Such a construction across iterations creates a ^3ERS that cannot be ...
    (sci.math)
  • Re: P is not equal to NP (and this is why)
    ... same way as a single edge, and a k-chromatic graph can be transformed ... In each even iteration of this ^3ERS, ... Such a construction across iterations creates a ^3ERS that cannot be ...
    (sci.math)
  • Re: a proof for consideration
    ... same way as a single edge, and a k-chromatic graph can be transformed ... initial vertex 4 and vertex 2 of that iteration. ... Such a construction across iterations creates a ^3ERS that cannot be ...
    (sci.math)
  • Re: a proof for consideration
    ... same way as a single edge, and a k-chromatic graph can be transformed ... initial vertex 4 and vertex 2 of that iteration. ... Such a construction across iterations creates a ^3ERS that cannot be ...
    (sci.math)