|
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. |
On September 29 2018 23:58 ZenithM wrote:
I mean the guy is an undergrad CS student, he probably just got introduced to Complexity 101 and thought it would be cool to prove P = NP without really knowing much else. Like hundreds of students before him :D. I remember back then the professor that was teaching us complexity theory told us he regularly received "proofs" of P vs NP and couldn't bother checking them anymore.
I have kinda had it with people coming in here to have their say smacking travis around. Clearly you haven't been around for very long, because travis has been asking increasingly complex questions and coming up with increasingly interesting solutions to problems for about a year or longer now. As I said about a year ago when this actually started, the chance that travis is actually onto a proof that P=NP is pretty slim, but I find it increasingly likely that he is at least onto some useful algorithms for solving specific classes of problems. And you're the second guy to come in here and say what a noob he is for even trying. Well, go fuck off.
(1) He undoubtedly already knows more about intricacies of the problem than I do (and I am not an undergrad CS student... I teach undergrad CS students, but not complexity theory).
(2) He is having fun and learning a lot from the whole process.
@travis: I know you don't need defending, and sorry if I come of as condescending doing so. I'm just tired of people talking trash of your work. As long as you are enjoying it and feel you are onto something, keep at it. I do think you should talk to a professor at your uni to get some pointers and supervision, but your question was specifically because that was already your intention, so keep it up!
|
On September 30 2018 00:07 travis wrote:Show nested quote +On September 29 2018 03:28 raNazUra wrote: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. 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).
Those conversions maintain complexity classes, though. That's the whole point, if I'm not mistaken. You're right though, they are (usually) not meant for application in practice, so finding good algorithms for HC etc. is a cool thing to try.
Of course if you're trying to implement a quick algorithm for solving HC on a limited set of graphs (say "easy" graphs or graphs with bounded amount of vertexes) then the actual running time matters and not the complexity class. But that just means you left the realm of P, NP, Exptime and PSpace having any meaning at all, because an algorithm in P can run much longer than one in say Exptime under these circumstances.
After all the complexity classes are just concerned with the approximative behaviour of the complexity mapped over increasing input "sizes" assuming worst case.
Finding neat algorithms to solve the problems in concrete cases is probably a more fruitful undertaking than actually trying to find a polynomial solution to any NP-hard/NP-complete problem. Then again how do you even make sure if your algorithm is in P if you do not analyze it by mathematical means? Or are you just trying to find an algorithm that terminates "quickly"?
|
On September 30 2018 02:52 Joni_ wrote:Show nested quote +On September 30 2018 00:07 travis wrote:On September 29 2018 03:28 raNazUra wrote: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. 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). Those conversions maintain complexity classes, though. That's the whole point, if I'm not mistaken. You're right though, they are (usually) not meant for application in practice, so finding good algorithms for HC etc. is a cool thing to try.
They supposedly maintain polynomial runtime, but many of the conversions increase N by some absurd amount. Like, N goes from 1000 to 1,000,000,000 - or something ridiculous like that.
Finding neat algorithms to solve the problems in concrete cases is probably a more fruitful undertaking than actually trying to find a polynomial solution to any NP-hard/NP-complete problem. Then again how do you even make sure if your algorithm is in P if you do not analyze it by mathematical means? Or are you just trying to find an algorithm that terminates "quickly"?
I honestly believe these problems are solvable in polynomial time, for philosophical reasons. I think that researchers are likely hampered by rigid thinking, which isn't meant as any disrespect because I think that rigid thinking can come as a natural result of developing a high level of knowledge of "rules" in a subject. But experts have been saying what can't be done since the beginning of civilization, only to be proven wrong... basically 100% of the time. Well obviously that's unfair hyperbole but there is a point there.
Regarding mathematical analysis, one of the reasons I am excited about what I am currently working on is that it actually does make a bit of sense to me mathematically. But normally I don't do much mathematical analysis. Both because it is hard for me, but also because I prefer to try to solve it conceptually and then mathematical analysis can come later. When I first started, I did come up with ideas I thought would be polynomial but were actually still exponential. However, I have gotten a lot better about quickly figuring out if something should be exponential or not.
On September 30 2018 02:52 Acrofales wrote:
(1) He undoubtedly already knows more about intricacies of the problem than I do (and I am not an undergrad CS student... I teach undergrad CS students, but not complexity theory).
(2) He is having fun and learning a lot from the whole process.
@travis: I know you don't need defending, and sorry if I come of as condescending doing so. I'm just tired of people talking trash of your work. As long as you are enjoying it and feel you are onto something, keep at it. I do think you should talk to a professor at your uni to get some pointers and supervision, but your question was specifically because that was already your intention, so keep it up!
I didn't take the commentary that hard because there is some truth to the criticisms my posts receive, even if they are a little condescending sometimes, because I think you are right about #1 - I likely know more about some of these problems than even most seasoned computer scientists, assuming they don't work in related fields.
I know sometimes the things I say come off as a little silly or naive but it is mostly due to enthusiasm, some people make big assumptions about how much I do or do not know. I really appreciate you saying something because I shrug off some of the hate, but I really get.. basically no encouragement from anywhere. I'm actually surprised that you said something so nice, not because I think you aren't nice, but because I think your post displayed an amount of clarity that I rarely expect to see. Thank you 
|
On September 30 2018 03:32 travis wrote:Show nested quote +On September 30 2018 02:52 Joni_ wrote:On September 30 2018 00:07 travis wrote:On September 29 2018 03:28 raNazUra wrote: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. 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). Those conversions maintain complexity classes, though. That's the whole point, if I'm not mistaken. You're right though, they are (usually) not meant for application in practice, so finding good algorithms for HC etc. is a cool thing to try. They supposedly maintain polynomial runtime, but many of the conversions increase N by some absurd amount. Like, N goes from 1000 to 1,000,000,000 - or something ridiculous like that.
Yes but thats the thing. A linear factor does not mean anything at all when talking about complexity classes (which you for sure are aware of). Complexity classes just dont make any meaningful statement about the runtime of an algorithm, only about change of runtime given increasing input sizes.
Show nested quote +Finding neat algorithms to solve the problems in concrete cases is probably a more fruitful undertaking than actually trying to find a polynomial solution to any NP-hard/NP-complete problem. Then again how do you even make sure if your algorithm is in P if you do not analyze it by mathematical means? Or are you just trying to find an algorithm that terminates "quickly"? I honestly believe these problems are solvable in polynomial time, for philosophical reasons. I think that researchers are likely hampered by rigid thinking, which isn't meant as any disrespect because I think that rigid thinking can come as a natural result of developing a high level of knowledge of "rules" in a subject. But experts have been saying what can't be done since the beginning of civilization, only to be proven wrong... basically 100% of the time. Well obviously that's unfair hyperbole but there is a point there.
Well for every "expert" (I hate that term because everyone can just claim to be an expert - at least in Germany it's not some protected term) that claims something cannot be done there is someone claiming to have found a solution or proof that turns out to be flawed.. :>
Nonetheless I admire your effort. I wish I was this fascinated by and dedicated to .. anything actually. I'm quite curious though: Is there a way for you to put into words why you are convinced that TSP is solvable in polynomial time?
|
No one has a clue about how to prove P vs NP either way and this is after decades of thousands of scientists banging their head into hundreds of NP problems from logistics to computer science to biology to maths for which no one has found a polynomial time solution.
Consdering that, I think it is realistic to state that P vs NP is not going to be solved by staring at some graphs for a while and just happening upon something everyone overlooked.
Moreover, P = NP would have such profound implications for every aspect of society, philosophy and science that I personally think there is no way it is true unless there is some huge undiscovered aspect of the universe. Which is again, not something you will discover by looking at graphs.
Having said that, what you're doing is by no means useless, I think it is a great learning opportunity even if your idea ends up not working. Or perhaps you will discover a speedup for certain cases of graphs. So by all means have at it, just don't get your hopes up too high  .
|
It is worth mentioning that people at universities are very used to people claiming to have solved popular unsolved problems, and usually the solutions are really silly. I talked about this to a few people at the maths department, and apparently they regularly get intricate letters with "solutions" to problems which have been proven to be unsolvable, like squaring the circle etc...
There is one guy who regularly hands out flyers at our physics faculty with alternate cosmological solutions to problems that require dark energy, which are so obviously flawed that even the students with a 2 ETCS astronomy course ca identify that the person has no idea what he is talking about, and in fact doesn't even realize what problems dark energy theories try to solve.
That is not to say that it couldn't be true in this case, (especially considering it is about an actually unsolved problem), and thinking about stuff is never a bad idea. Statistics suggest that it is unlikely to find a solution to a very complex problem that the thousands of people whose job it is to think about stuff haven't thought about so far, but it is not impossible.
Just don't run into a university and claim that you totally solved it with some proof that is obviously not a proof.
|
On September 30 2018 03:55 Joni_ wrote:
Nonetheless I admire your effort. I wish I was this fascinated by and dedicated to .. anything actually. I'm quite curious though: Is there a way for you to put into words why you are convinced that TSP is solvable in polynomial time?
Well, I think that the universe is governed by cause and effect, and that cause and effect can be solved by investigating patterns. For NP-Complete problems, all of the information is available. The patterns are there, I just think we need to solve them. Or, we may not even need to do that.
Right now, we just simply haven't figured out the patterns... so the conclusion has mostly been that there is no way other than explicitly calculating deeper and deeper combinations. But I haven't seen any argument why P != NP other than that "well we tried so many things that didn't work that we have given up".
On September 30 2018 05:57 solidbebe wrote:
No one has a clue about how to prove P vs NP either way and this is after decades of thousands of scientists banging their head into hundreds of NP problems from logistics to computer science to biology to maths for which no one has found a polynomial time solution.
I've learned to form my beliefs based on my own conclusions.
Consdering that, I think it is realistic to state that P vs NP is not going to be solved by staring at some graphs for a while and just happening upon something everyone overlooked.
I am not sure what the point of saying this is.
Moreover, P = NP would have such profound implications for every aspect of society, philosophy and science that I personally think there is no way it is true unless there is some huge undiscovered aspect of the universe. Which is again, not something you will discover by looking at graphs.
Since when is "it'll change the status quo" evidence that something is or isn't possible? To date, the strongest evidence I have seen that it isn't possible is that machine learning hasn't solved it.
And, I don't think you are trying to be rude, but this "by just looking at graphs" stuff comes off as condescending, especially since you don't know what I spend my time doing.
|
If only Neumann hadn't bit the dust when he did, chances are he might have solved P=NP, after all, Godel did send him a letter about it on his deathbed.
Somewhat surprised they didn't stick with rust, given how good it is with modularizing things by rust version. Though, if they were having trouble getting good c++ engineers, I can't imagine how they'd fare with good rust programmers.
|
On September 30 2018 12:00 bo1b wrote:
Somewhat surprised they didn't stick with rust, given how good it is with modularizing things by rust version. Though, if they were having trouble getting good c++ engineers, I can't imagine how they'd fare with good rust programmers.
I basically have no idea about rust, but anyways: I would imagine that the trouble with finding good C++ engineers is not because of a lack of quantity of C++ engineers, but because of a lack of quality. Getting good at C++ is much harder than getting good at most other, newer languages. Training people to be good rust engineers sounds much easier than training people to be good C++ engineers, and a lot more people have the potential to even reach that level of quality if the language is easier (I'd say that only a small number of people even has the theoretical ability to get good at C++). Cost might also be an issue. Good C++ programmers usually are seasoned developers who will obviously ask for higher pay based on their experience.
|
I did mention good c++ developers specifically. And yeh, good c++ developers are pretty much monopolised by 4 companies commanding stupendous salaries.
As to the ease of rust vs c++, I'm not honestly convinced. Rust is in a weird spot, difficulty wise. It's just like c/c++ in low levelness, but it also has some really high end features you'd only really expect to see in a theoretical functional language, like haskell. I guess it depends what you associate the difficulty in c++ with, and if it's accounting for 40 years of kitchen sinks thrown in vs template metaprogramming and manual memory management. The former I don't think any language has a claim to, the latter is a bit more subjective.
|
On September 30 2018 08:25 travis wrote:Show nested quote +On September 30 2018 03:55 Joni_ wrote:
Nonetheless I admire your effort. I wish I was this fascinated by and dedicated to .. anything actually. I'm quite curious though: Is there a way for you to put into words why you are convinced that TSP is solvable in polynomial time? Well, I think that the universe is governed by cause and effect, and that cause and effect can be solved by investigating patterns. For NP-Complete problems, all of the information is available. The patterns are there, I just think we need to solve them. Or, we may not even need to do that. Right now, we just simply haven't figured out the patterns... so the conclusion has mostly been that there is no way other than explicitly calculating deeper and deeper combinations. But I haven't seen any argument why P != NP other than that "well we tried so many things that didn't work that we have given up".
I.. dont quite get what youre trying to say there? Why would the existence of a pattern imply the computability of said pattern to be of complexity P?
I mean there are problems in Exptime that are also governed by cause and effect, that provably do not possess a polynomial solution. I'm not quite sure what you mean by all information being available. Is all information available for the "halting in k steps" problem? (I think that was the classic example of an Exptime-complete problem? Idk, complexity theory is not my strong suite, I'm from pure maths..)
|
On September 30 2018 15:55 bo1b wrote:
I did mention good c++ developers specifically. And yeh, good c++ developers are pretty much monopolised by 4 companies commanding stupendous salaries.
As to the ease of rust vs c++, I'm not honestly convinced. Rust is in a weird spot, difficulty wise. It's just like c/c++ in low levelness, but it also has some really high end features you'd only really expect to see in a theoretical functional language, like haskell. I guess it depends what you associate the difficulty in c++ with, and if it's accounting for 40 years of kitchen sinks thrown in vs template metaprogramming and manual memory management. The former I don't think any language has a claim to, the latter is a bit more subjective.
I don't think the biggest problem is in actually writing C++ code. The biggest problem seems to be maintainability of said code. You get a lot of libraries, some of them not compatible with each other, updating old code to newer standards can be a lot of pain and getting your project in order for any large product just takes a lot of effort and time.
I guess that people are moving to other languages because they think that taking a loss in program execution speed will be well worth it in development cycle gains.
|
I think c++ has a lot of challenges tbh, it's a bad sign when the company with probably the best and most c++ programmers on the planet has a style guide preventing use of a noticeable chunk of the language.
It's also a beurocracy beyond belief, in an environment where it really doesn't need to be, and despite every check and balance in the world being used by the development team, it's still waded down with so much crap that simply doesn't need to be their - except that one guy who for whatever reason felt compelled to use it 15 years ago, and now the entire tool chain can't afford to move away from that feature.
I can definitely see why people are moving away from it, even though I despise the trend of moving towards slow, bloated languages and javascript in particular. But hey, we have way faster processors now, with a million cores, and parallelism isn't exactly simple in c++ to set up compared to say, go.
Also, https://en.wikipedia.org/wiki/Wirth's_law + electron haha
|
On September 30 2018 02:52 Acrofales wrote:Show nested quote +On September 29 2018 23:58 ZenithM wrote:
I mean the guy is an undergrad CS student, he probably just got introduced to Complexity 101 and thought it would be cool to prove P = NP without really knowing much else. Like hundreds of students before him :D. I remember back then the professor that was teaching us complexity theory told us he regularly received "proofs" of P vs NP and couldn't bother checking them anymore. I have kinda had it with people coming in here to have their say smacking travis around. Clearly you haven't been around for very long, because travis has been asking increasingly complex questions and coming up with increasingly interesting solutions to problems for about a year or longer now. As I said about a year ago when this actually started, the chance that travis is actually onto a proof that P=NP is pretty slim, but I find it increasingly likely that he is at least onto some useful algorithms for solving specific classes of problems. And you're the second guy to come in here and say what a noob he is for even trying. Well, go fuck off. (1) He undoubtedly already knows more about intricacies of the problem than I do (and I am not an undergrad CS student... I teach undergrad CS students, but not complexity theory). (2) He is having fun and learning a lot from the whole process. @travis: I know you don't need defending, and sorry if I come of as condescending doing so. I'm just tired of people talking trash of your work. As long as you are enjoying it and feel you are onto something, keep at it. I do think you should talk to a professor at your uni to get some pointers and supervision, but your question was specifically because that was already your intention, so keep it up!
I do now think he's aware of the difficulty of what he's trying to do. His messages at first really read like "I looked at some graphs and it works", hence my scepticism.
But what I was hinting at in my first post to him (not the snarky one, the previous one, where I tried to be helpful), is that there are more interesting things in CS than chasing the golden goose of P vs NP. If he's really as talented as you think he is, he would probably be better off working on something else.
And spare me with the "I teach undergrad CS students". From experience you really don't need to be any good to do that. Nobody is impressed.
|
Speaking of more interesting things in CS, what "new" fields do you think might be taking off in the future, not including A.I.
|
Transportation and logistics should be interesting. Specialized tools for different use cases, such as lock boxes in an automatic car for pizza deliveries.
3d printing and food manufacturing. Possibly we could eventually print edible food stuffs out of stored blocks of different materials? Simply get a block of carbon delivered every month, and rarer elements every few months, print a pear out and eat it.
Similarly, nanofactories.
Many of these things are CS combined with other fields, but... that's true of all CS.
|
Cloud computing and cloud solutions for scaling applications is a thing now too. Many web servers are moving to the cloud now and stuff like Docker, Kubernetes, AWS etc. are the thing.
|
Yeah i have my doubts about 3d printers, there is something called "specialization law" in manufacturing which states that the more specific and narrow purpose of the machine the more efficient it can be therefore 3d printers as general purpose machines will always be less efficient than specialized machines. They have their uses of course but wherever efficiency is more important than versality they wont find its place.
Virtualization, data analysis and quantum computing is the future i guess.
And regarding quantum computing, recently i attended a lecture about it by friend of mine which works PAN (Polish research institute) and one of the most interesting thing which he said is that there seem to be some fundamental physical obstacle to the speed with which state can be changed (if i understand him correctly) which means that our hopes of instantaneous (or near) instantaneous solution to some problems are gone. The quantum computing still will be much faster in some areas but not to level we were hoping for.
Edit:spelling
|
On October 02 2018 20:14 Silvanel wrote:
Yeah i have my doubts about 3d printers, there is something called "specialization law" in manufacturing which states that the more specific and narrow purpose of the machine the more efficient it can be therfore 3d printers as general purpose machines will always be less efficient than specialized machines. There have their uses of course but wherever efficiency is more important than versality they wont find its place.
Virtualization, data analysis and quantum computing is the future i guess.
Dunno when 3D printers became a topic, but they do have a focused purpose: prototyping and specialised low quantity products. Of course they're never going to be more effecient at making high quantity (or even quality) products than a specialised machine
|
I'm honestly fascinated by biotechnology. Really considering attempting to pivot into that field.
|
|
|
|
|
|
EPT
