EPT![[image loading]](https://www.wykop.pl/cdn/c3201142/comment_Xm5qif8rs5M3pf2nLcSFkKrZi36Jqhe2.jpg)
The Big Programming Thread - Page 973
| Forum Index > General Forum |
Thread Rules 1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution. 2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20) 3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible. 4. Use [code] tags to format code blocks. | ||
|
Manit0u
Poland17614 Posts
| ||
|
Deleted User 3420
24492 Posts
And yes, I am talking a solution not an approximation or heuristic. I think I would like to go to my school, University of Maryland College Park, to get assistance with investigating this. Particularly, the math heavy side, and doing proofs. I was wondering if anyone had advice as to how I can ensure that credit for my discoveries is not taken from me, because that is not something I would like to risk. | ||
|
solidbebe
Netherlands4921 Posts
edit*I confused NP-hard with NP-complete.. mah bad. | ||
|
Simberto
Germany11722 Posts
On September 26 2018 04:11 travis wrote: I've discovered a solution for multiple problems that are currently considered NP hard (minimum vertex cover/perfect matching, hamiltonicity). It works for many graphs, and I have just started delving into it - I believe I may be able to extend it to a generalized solution.... or it may pretty much already be. Like I said, just started getting into it. And yes, I am talking a solution not an approximation or heuristic. I think I would like to go to my school, University of Maryland College Park, to get assistance with investigating this. Particularly, the math heavy side, and doing proofs. I was wondering if anyone had advice as to how I can ensure that credit for my discoveries is not taken from me, because that is not something I would like to risk. You could do the thing where you write down the core ideas, and leave that in a closed envelope with a date on it at a notary or something. | ||
|
Deleted User 3420
24492 Posts
| ||
|
solidbebe
Netherlands4921 Posts
Just to be clear though... if you say you think you've found a polynomial time solution for NP-hard problems, then that would mean you've proved P=NP. You realize the implications here right? Let me just say it is extremely unlikely your idea works.. | ||
|
Deleted User 3420
24492 Posts
| ||
|
Acrofales
Spain18195 Posts
| ||
|
Manit0u
Poland17614 Posts
You'd be amazed... | ||
|
Deleted User 3420
24492 Posts
favorite part of that is how many of those passwords are highly secure in terms of password strength. they'll never be brute forced! | ||
|
Excludos
Norway8231 Posts
| ||
|
ZenithM
France15952 Posts
On the polynomial-time solution to NP-hard problems, you should note that it's easy to naturally come up with instances that are solvable by some seemingly algorithmic method efficiently. Especially for small-size instances. Needless to say, said method would have to work on every instance no matter what. And this requires proof infinitely more than testing on some instances, as I'm sure you're aware. Edit: actually found an interesting paragraph on the idea that most instances you come up with could be "easy": https://en.m.wikipedia.org/wiki/P_versus_NP_problem#P_≠_NP ( part talking about average-case complexity) The likelihood of you finding a general constructive solution in P (implying that P=NP) by just looking at some graphs and see that "it works" seems very small to me. And I'm definitely not saying that to make fun of you or belittle your efforts, just saying you'll have a long road (very likely fruitless) ahead of you if that's where you're at right now. First thing I would do if I were you if you didn't already do it, is implement your solution, to the Traveling Salesman problem and test it on large instances you can find on the Internet (usually used to assess the many heuristical solutions people have come up with over the years). Short of proving anything, testing it on a large number of arbitrary complex instances might help you at least believe in yourself :D (or crush your hopes early). Anyway if society collapses because of my guy Travis, MOM I WAS THERE, SHOUTOUT!!! | ||
|
Deleted User 3420
24492 Posts
On September 28 2018 01:44 ZenithM wrote: @travis On the polynomial-time solution to NP-hard problems, you should note that it's easy to naturally come up with instances that are solvable by some seemingly algorithmic method efficiently. Especially for small-size instances. I learned that the hard way! lol I've been doing this for a good while now, it's what I've spent the vast majority of my time on for the last year now. I've actually thought I just about had or did have a solution several times now. Only to find out that it won't work under some condition which starts appearing more and more as the graphs grow big. Right now I use this data set of 1001 difficult graphs: http://www.flinders.edu.au/science_engineering/csem/research/programs/flinders-hamiltonian-cycle-project/fhcpcs.cfm I typically run mostly the smallest graphs (N=66 to ~300), because even cubic algorithms start taking up a lot of space and time when N is very high (thousands), and I want to save time during testing. I'll test in the thousands when an algorithm is optimized and I am confident in it. This is hard for me to do much testing and development because a lot is going on in school and im trying hard not to fail while working on this. So, movement is slow. Needless to say, said method would have to work on every instance no matter what. And this requires proof infinitely more than testing on some instances, as I'm sure you're aware. Edit: actually found an interesting paragraph on the idea that most instances you come up with could be "easy": https://en.m.wikipedia.org/wiki/P_versus_NP_problem#P_≠_NP ( part talking about average-case complexity) Well, what I find might not work on a big set of instances because those instances need extra steps - something else has to be done. So I think a method that works for every subset under some rules is super valuable. In fact, my gut says that anything I find that is useful will likely need extra steps to handle different types of graphs. The likelihood of you finding a general constructive solution in P (implying that P=NP) by just looking at some graphs and see that "it works" seems very small to me. And I'm definitely not saying that to make fun of you or belittle your efforts, just saying you'll have a long road (very likely fruitless) ahead of you if that's where you're at right now. I've been on it for a while  . Literally 50+ hours a week for almost every week for the last year. I can handle getting my hopes crushed repeatedly, getting my naivety stomped out.First thing I would do if I were you if you didn't already do it, is implement your solution, to the Traveling Salesman problem and test it on large instances you can find on the Internet (usually used to assess the many heuristical solutions people have come up with over the years). Short of proving anything, testing it on a large number of arbitrary complex instances might help you at least believe in yourself :D (or crush your hopes early). i am working on the hamiltonian cycle problem right now actually, not TSP. I do believe TSP will end up being a much more difficult problem than hamiltonian cycle. | ||
|
ZenithM
France15952 Posts
Good luck! | ||
|
Apom
France656 Posts
On September 26 2018 04:11 travis wrote: Pro tip : you have not.I've discovered a solution for multiple problems that are currently considered NP hard (minimum vertex cover/perfect matching, hamiltonicity). But hey, as long as you are having fun... | ||
|
Manit0u
Poland17614 Posts
| ||
|
ZenithM
France15952 Posts
| ||
|
raNazUra
United States10 Posts
i am working on the hamiltonian cycle problem right now actually, not TSP. I do believe TSP will end up being a much more difficult problem than hamiltonian cycle. This is a bit of a mistake. The whole point of NP-complete problems is that if you can solve one, you've solved them all. The transformation between them is already discovered. It may be circuitous, but it exists and is known. | ||
|
ZenithM
France15952 Posts
| ||
|
Deleted User 3420
24492 Posts
On September 29 2018 03:28 raNazUra wrote: This is a bit of a mistake. The whole point of NP-complete problems is that if you can solve one, you've solved them all. The transformation between them is already discovered. It may be circuitous, but it exists and is known. Well, what currently exists is completely absurd, and I haven't even heard of it being done in practice. The *only* conversion I have heard of is TSP --> sat --> 3sat ---> vertex cover ---> HC, and you'll end up with a hilariously large HC problem. So, when I say "more difficult", I am probably misusing language, but I didn't necessarily mean polynomial vs exponential time (or whatever other technical metrics there are). | ||
| ||
