Computer Science – Computational Complexity
Scientific paper
2008-12-17
Computer Science
Computational Complexity
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
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.
Profile ID: LFWR-SCP-O-94491