Ivan, Think of it like so. If you have some algo solving some problem -- doesn't matter what, AI or not AI, opencog or not opencog, anything -- and you make the problem N times bigger, how much longer does it take to solve it? (say twice as big, or three times as big or just N times bigger...)
If you make it twice as big, and it takes the same amount of time, that's "constant time" and is written O(1) For example, access to an array or vector is O(1), does not depend on the vector size. If you make it twice as big, and it takes twice as long, that's linear. its written O(N) For example, walking a linked list is O(N) -- make it twice as long, you have twice as many steps to get to the end. Some problems are quadratic -- O(N^2) Some problems are cubic -- O(N^3) -- most parsers, of any kind, are O(N^3) -- basically, you can't beat that, its a kind of a best-possible performance. In general, write O(N^y) for some number y. If y is less than infinity, then the problem is "polynomial" or P But it could happen that the algorithm is O(N^N) or O(exp(N)) or O(N!) that is, N-factorial. These are examples of non-polynomial or NP algorithms. So P=NP says, for every problem, there exists some (maybe unknown) algorithm that solves it in P time. i.e. in O(N^y) for some number y. Three problems: a) it seems very very unlikely that P=NP b) Even if P=NP, you probably still won't know what the best algo actually is. c) The number y could still be large. I read a paper yesterday for an algo that is O(N^7) which is pretty useless -- if my problem takes an minute of CPU time, and making it twice as big makes it run for 2^7= 128 minutes (two hours) that is pretty useless. If I make it three times as big, 3^7=2187 minutes = 1.5 days!! Conclusion P=NP and/or P != NP is pretty much totally useless for practical work. You may as well be designing a spaceship to fly to the center of the galaxy. Its fun -- can't knock it -- do something fun, but it doesn't matter for actually writing any actual code. --linas On Tue, Nov 6, 2018 at 11:00 AM Ivan Vodišek <[email protected]> wrote: > Hello everyone :) > > I have a question regarding to my independent research relating to > OpenCog. I read somewhere (I really don't remember where) that if P = NP > <https://en.wikipedia.org/wiki/P_versus_NP_problem> then it would be > beneficial to AI in general. > > There are science fields which would obviously benefit if P = NP. But my > question is: how would specifically OpenCog benefit from that solution? > Somehow, it should be a matter of reducing a large number of possible > combinations, but I don't really see were would AI fit into this equation. > Googling around didn't produce anything interesting, so I'm making a post > to this OpenCog community in a hope for an answer. > > Thank you all for your time, > Ivan V. > > -- > You received this message because you are subscribed to the Google Groups > "opencog" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > Visit this group at https://groups.google.com/group/opencog. > To view this discussion on the web visit > https://groups.google.com/d/msgid/opencog/CAB5%3Dj6W5UhHawabD6NAyT7hEMfkJNCAhd%2BzJcXgFZpJu-MhoMg%40mail.gmail.com > <https://groups.google.com/d/msgid/opencog/CAB5%3Dj6W5UhHawabD6NAyT7hEMfkJNCAhd%2BzJcXgFZpJu-MhoMg%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > For more options, visit https://groups.google.com/d/optout. > -- cassette tapes - analog TV - film cameras - you -- You received this message because you are subscribed to the Google Groups "opencog" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/opencog. To view this discussion on the web visit https://groups.google.com/d/msgid/opencog/CAHrUA347XQjxyfmFdPj2wf_SADJVSk_ehO0vwzrjLNxK%3DeEevg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
