Two conjectures such that the proof of any one of them will lead to the proof that P = NP

Computer Science – Computational Complexity

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Some minor corrections

Scientific paper

In this paper we define a construct called a time-graph. A complete time-graph of order n is the cartesian product of a complete graph with n vertices and a linear graph with n vertices. A time-graph of order n is given by a subset of the set of edges E(n) of such a graph. The notion of a hamiltonian time-graph is defined in a natural way and we define the Hamiltonian time-graph problem (HAMTG) as : Given a time-graph is it hamiltonian ? We show that the Hamiltonian path problem (HAMP) can be transformed to HAMTG in polynomial time. We then define certain vector spaces of functions from E(n) and E(n)xE(n) to B = {0,1}, the field of two elements and derive certain properties of these spaces. We give two conjectures about these spaces and prove that if any one of these conjectures is true, we get a polynomial time algorithm for the Hamiltonian path problem. Since the Hamiltonian path problem is NP-complete we obtain the proof of P = NP provided any one of the two conjectures is true.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Two conjectures such that the proof of any one of them will lead to the proof that P = NP does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Two conjectures such that the proof of any one of them will lead to the proof that P = NP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two conjectures such that the proof of any one of them will lead to the proof that P = NP will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-94491

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.