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.
