I understand. It is like restricting input to a disjunctive normal form subset of formulas that would produce a SAT results in constant / linear time.
Once I saw an interesting discussion about a specific brute force assembler optimizer. Optimizer was taking an input domain and a short piece of code that operates over that domain, pairing it with codomain values (complete definition of an arbitrary algorithm). Then it was constructing a different combinations of instruction sequences that behave exactly as the starting program, but happen to be either smaller, or faster than the original code. This brute force optimizer was a successful experiment, it produced more optimized (actually the most optimized because it exhausted all the combinations) versions of code, but was explodingly slow for programs larger than some 12, or so instructions, being ran on a regular PC. I wonder what could be done with supercomputers running that experiment? čet, 8. stu 2018. u 15:33 'Nil Geisweiller' via opencog < [email protected]> napisao je: > On 11/8/18 11:25 AM, Ivan Vodišek wrote: > > 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. > > True. > > When I say subclass of inputs, I literally mean inputs, so if say f is > a function in NP, there is some subclass of x, S, such that for all x > in S, T(f(x)) = O(|x|^n). An obviously subclass would be where |x| is > bound, but that's of course not interesting. > > Or one could consider the complexity over a sequence of inputs, where > only incremental costs are considered. > > I guess it means that there are multiple ways to crack P = NP other > than in its full generality that can still be useful. > > Nil > > > > > čet, 8. stu 2018. u 07:17 'Nil Geisweiller' via opencog > > <[email protected] <mailto:[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]> > > <mailto:[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:opencog%[email protected] > > <mailto:opencog%[email protected]>> > > > > <mailto:[email protected] > > <mailto:opencog%[email protected]> > > > <mailto:opencog%[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]>> > > > > <mailto:[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]> > > > <mailto:opencog%[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/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: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%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] > > <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/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] > > <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%3Dj6XkQL2voYguNkCQemWsYuX%2BcamVC7qDGFzjSSyeti0V5w%40mail.gmail.com > > < > https://groups.google.com/d/msgid/opencog/CAB5%3Dj6XkQL2voYguNkCQemWsYuX%2BcamVC7qDGFzjSSyeti0V5w%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/d7b953fa-07e9-96a4-3fe5-bc66a24fadc2%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%3Dj6VZ6wx%2BM6wt0G8_ZZ2LuKnT0trcLZRvrPk8_ugM9Jc-rw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
