3 ms·

I spent some forty minutes on this, I think his "multistage graph simple path problem" is a very obfuscated version of a simpler problem where there is no need

by stiff 13y ago

I spent some forty minutes on this, I think his "multistage graph simple path problem" is a very obfuscated version of a simpler problem where there is no need for this complicated labelling of vertices, with the information being instead reflected in the connections between vertices. I think the problem he discusses is simply the problem of determining whether two vertices in a graph are connected via a path or not. Did anyone else understand his problem formulation and had any similar impressions? I have a microscopic hope of this being a valid P=NP proof, still would be nice to know wtf is this about.

ColinWright 13y ago
His "Multistage Graph" seems poorly defined. I'm slowly coming to grasp what I think it is, but he defines is as G = <V,E,S,D,L> but pulls the E(v) from nowhere. It's not looking good.
- stiff 13y ago
  Yes, I think the intention is for E(v) to be one of the inputs of the algorithm (I contemplated E(v) for half an hour to guess this is what he means). I thought maybe the following is possible: I create a new graph with the same vertices as his graph, but instead of having an E(v) I connect each vertex to the members of E(v) via an edge. Afterwards, if two vertices are not connected via an edge in his original graph, I remove this edge from my new graph. I cannot really get to the heart of it, I just had a vague impression this might be equivalent, either way I think the problem could likely be formalized in a more effective way.
usamec 13y ago
Nope, there are constrains on how the path might look or not. The constrains have form: Is path enters vertex v, then it might only use edges {...}.
- ColinWright 13y ago
  Yes - it's getting harder and harder to pin down exactly what this problem really is, what an example of it is really like, and what's really going on. I'm sure the author has something in mind. I'm sure it's not well explained, and it might even prove insufficiently explained to be able to assess it properly. It's looking like it's locally "OK" but globally nonsense.
  - usamec 13y ago
    Well, he get proving that his problem is NP-hard right (because the proof is really easy). But his algorithm for solving his problem is really messy and hard to follow.

by stiff 13y ago

ColinWright 13y ago

His "Multistage Graph" seems poorly defined. I'm slowly coming to grasp what I think it is, but he defines is as G = <V,E,S,D,L> but pulls the E(v) from nowhere. It's not looking good.

stiff 13y ago
Yes, I think the intention is for E(v) to be one of the inputs of the algorithm (I contemplated E(v) for half an hour to guess this is what he means). I thought maybe the following is possible: I create a new graph with the same vertices as his graph, but instead of having an E(v) I connect each vertex to the members of E(v) via an edge. Afterwards, if two vertices are not connected via an edge in his original graph, I remove this edge from my new graph. I cannot really get to the heart of it, I just had a vague impression this might be equivalent, either way I think the problem could likely be formalized in a more effective way.

usamec 13y ago

Nope, there are constrains on how the path might look or not. The constrains have form: Is path enters vertex v, then it might only use edges {...}.

ColinWright 13y ago
Yes - it's getting harder and harder to pin down exactly what this problem really is, what an example of it is really like, and what's really going on. I'm sure the author has something in mind. I'm sure it's not well explained, and it might even prove insufficiently explained to be able to assess it properly. It's looking like it's locally "OK" but globally nonsense.
- usamec 13y ago
  Well, he get proving that his problem is NP-hard right (because the proof is really easy). But his algorithm for solving his problem is really messy and hard to follow.