3
$\begingroup$

Is there a concept for comparing algorithms in artificial intelligence theory similar to reduction in complexity theory (Wikipedia)?


I'm asking this because I was wondering how AI algorithms are to be classified in terms of general applicability. As far as I'm aware, AI techniques are largely classified by which problem they are solving rather than how abstract/ general they are. To me, it would make sense to classify algorithms $P$ and $Q$ for different problems in terms of generality by determining whether $P$ can also—potentially by means of a prior transformation of the input—solve $Q$.

Articles and book references are very welcome!

$\endgroup$
  • $\begingroup$ How can one problem solve another? What does that mean in terms of sets? What does it mean, practically speaking, for an algorithm to be "more generally applicable" than another? $\endgroup$ – Raphael Sep 20 '16 at 23:27
  • $\begingroup$ I'm not sure if these are rhetorical questions, so here goes: (1) I'm not talking about "one problem solving another" but rather about a technique/algorithm for solving one problem also being applicable to solving another problem. (2) In terms of sets $S_P \supseteq S_Q$ for the set $S_P$ of the problems solvable by way of transforming $P$ (similarly for $S_Q$). (3) An algorithm $P$ is more generally applicable than an algorithm $Q$ if $P$—potentially by way of transformation within a given complexity threshold— may be applied to more problems. $\endgroup$ – FK82 Sep 21 '16 at 12:32
  • 1
    $\begingroup$ Can please give helpful example of what you mean? I think you are using some terms in particular, intuitive ways that may not match common definitions; it's therefore hard to answer. $\endgroup$ – Raphael Sep 21 '16 at 13:19
  • 1
    $\begingroup$ Then maybe you should ask that question instead of fumbling to formalize something. ;) $\endgroup$ – Raphael Sep 21 '16 at 14:28
  • 1
    $\begingroup$ @FK82 There is no such notion in complexity theory; we compare problems there. Therefore, you'll have to explain from scratch what kind of relation you mean. $\endgroup$ – Raphael Sep 21 '16 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.