By definition, NP-complete problems are such NP problems to which any other NP problem can be reduced in polynomial time. There are proven numerous NP-complete problems (Boolean SAT and Traveling salesman being some of them), and if we would solve any of them, we would automatically cover the whole set of NP.
čet, 8. stu 2018. u 07:17 'Nil Geisweiller' via opencog < [email protected]> napisao je: > Hello, > > On 11/7/18 4:44 PM, Ivan Vodišek wrote: > > My approach is to manually resolve some NP complete > > <https://en.wikipedia.org/wiki/NP-completeness> problems such are > > Boolean SAT or Traveling salesman in polynomial time. I have some > > indices that it is a possible task. > > I suspect you'd only discover subclasses of inputs for which P = NP. > But that doesn't mean it wouldn't be useful or insightful. > > > (My apologies to Singularity.net > > crew due to mess that P = NP would do to AGI Coin. But there are so much > > Quite the contrary, any knowledge that can be used to decrease > algorithmic complexity is extremely welcome. Consider that you're > talking to people who are banging their heads against the wall of > complexity on a daily basis. ;-) > > Nil > > > > > > > Obviously for a finite set of inputs, one can turn any complex > > algorithm into a logarithmic one (think of a pre-calculated binary > > decision tree, where each branch is a bit describing the input and > > each leaf is the solution). But it should still be possible to learn > > an actual algorithm rather than a finite giant decision tree, that > > performs worse that log, is more compact, but performs better than NP > > for a bunch of real-world problems. > > > > > > I think of algorithms as a possible compressed forms of their output. > > > > sri, 7. stu 2018. u 14:19 'Nil Geisweiller' via opencog > > <[email protected] <mailto:[email protected]>> napisao je: > > > > Hello Ivan, > > > > If P = NP it would mean that, given a problem reframed as reasoning > > such that its solution is a proof p of size s, one could construct p > > in a polynomial time of s, which sounds very doubtful. > > > > That's in theory, in practice however I think we could make P = NP > for > > some class of inputs via clever use of meta-learning (such as > > inference control meta-learning that we're experimenting within > > opencog, see > > > https://blog.singularitynet.io/introspective-reasoning-within-the-opencog-framework-1bc7e182827 > ). > > > > In fact I had this dream where we could have a sequence of NP > problems > > and progressively learn how to solve them in P. > > > > Obviously for a finite set of inputs, one can turn any complex > > algorithm into a logarithmic one (think of a pre-calculated binary > > decision tree, where each branch is a bit describing the input and > > each leaf is the solution). But it should still be possible to learn > > an actual algorithm rather than a finite giant decision tree, that > > performs worse that log, is more compact, but performs better than NP > > for a bunch of real-world problems. > > > > Nil > > > > On 11/6/18 7:00 PM, Ivan Vodišek 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] > > <mailto:opencog%[email protected]> > > > <mailto:[email protected] > > <mailto:opencog%[email protected]>>. > > > To post to this group, send email to [email protected] > > <mailto:[email protected]> > > > <mailto:[email protected] <mailto:[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. > > > > -- > > 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] > > <mailto:opencog%[email protected]>. > > To post to this group, send email to [email protected] > > <mailto:[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/e1418e0e-8604-2421-0597-4846a7644d3c%40gmail.com > . > > For more options, visit https://groups.google.com/d/optout. > > > > -- > > 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] > > <mailto:[email protected]>. > > To post to this group, send email to [email protected] > > <mailto:[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%3Dj6W6GfPkQpUM0i_g6LjwBERf0XM906p%2B7rTn-nvRvPEZ7Q%40mail.gmail.com > > < > https://groups.google.com/d/msgid/opencog/CAB5%3Dj6W6GfPkQpUM0i_g6LjwBERf0XM906p%2B7rTn-nvRvPEZ7Q%40mail.gmail.com?utm_medium=email&utm_source=footer > >. > > For more options, visit https://groups.google.com/d/optout. > > -- > 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/fed0d09b-3f8d-91a3-3cfd-875de0c45c96%40gmail.com > . > For more options, visit https://groups.google.com/d/optout. > -- 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%3Dj6XkQL2voYguNkCQemWsYuX%2BcamVC7qDGFzjSSyeti0V5w%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
