Relevancy in Problem Solving: A Computational Framework

Kwisthout, Johan
October 2012
Journal of Problem Solving;Fall2012, Vol. 5 Issue 1, p18
Academic Journal
When computer scientists discuss the computational complexity of, for example, finding the shortest path from building A to building B in some town or city, their starting point typically is a formal description of the problem at hand, e.g., a graph with weights on every edge where buildings correspond to vertices, routes between buildings to edges, and route-distances to edge-weights. Given such a formal description, either tractability or intractability of the problem is established, by proving that the problem either enjoys a polynomial time algorithm or is NP-hard. However, this problem description is in fact an abstraction of the actual problem of being in A and desiring to go to B: it focuses on the relevant aspects of the problem (e.g., distances between landmarks and crossings) and leaves out a lot of irrelevant details. This abstraction step is often overlooked, but may well contribute to the overall complexity of solving the problem at hand. For example, it appears that "going from A to B" is rather easy to abstract: it is fairly clear that the distance between A and the next crossing is relevant, and that the color of the roof of B is typically not. However, when the problem to be solved is "make X love me", where the current state is (assumed to be) "X doesn't love me", it is hard to agree on all the relevant aspects of this problem. In this paper a computational framework is presented in order to formally investigate the notion of relevance in finding a suitable problem representation. It is shown that it is in itself intractable in general to find a minimal relevant subset of all problem dimensions that might or might not be relevant to the problem. Starting from a computational complexity stance, this paper aims to contribute a computational framework of 'relevancy' in problem solving, in order to be able to separate 'easy to abstract' from 'hard to abstract' problems. This framework is then used to discuss results in the literature on representation, (insight) problem solving and individual differences in the abstraction task, e.g., when experts in a particular domain are compared with novice problem solvers.


Related Articles

  • Mathematical Abstraction in the Solving of Ill-Structured Problems by Elementary School Students in Korea. Jee Yun Hong; Kyeong Kim // Eurasia Journal of Mathematics, Science & Technology Education;Feb2016, Vol. 12 Issue 2, p267 

    Ill-structured problems can be regarded as one of the measures that meet recent social needs emphasizing students' abilities to solve real-life problems. This study aimed to analyze the mathematical abstraction process in solving such problems, and to identify the mathematical abstraction level...

  • The Complexity of Compressed Membership Problems for Finite Automata. Jeż, Artur // Theory of Computing Systems;Nov2014, Vol. 55 Issue 4, p685 

    In this paper, a compressed membership problem for finite automata, both deterministic (DFAs) and non-deterministic (NFAs), with compressed transition labels is studied. The compression is represented by straight-line programs (SLPs), i.e. context-free grammars generating exactly one string. A...

  • Computational thinking: a discipline with uses outside the computer lab? Richards, Justin // Computer Weekly;6/26/2007, p52 

    The article presents the views expressed by the British Computer Society Thought Leadership debate participants on computational thinking. One attendee said that computational thinking should be seen as being a common language for solving problems, one which helps iron out the problems from...

  • Explaining Results of Artificial Neural Networks. Yedjour, D.; Yedjour, H.; Benyettou, A. // Journal of Applied Sciences;2011, Vol. 11 Issue 15, p2855 

    Neural networks are very efficient in solving various problems but they have no ability of explaining their answers and presenting gathered knowledge in a comprehensible way. Two main approaches are used, namely the pedagogical one that treats a network as a black box and the local one that...

  • A Strong Designated Verifiable DL Based Signcryption Scheme. Mohanty, Sujata; Majhi, Banshidhar // Journal of Information Processing Systems;Dec2012, Vol. 8 Issue 4, p567 

    This paper presents a strong designated verifiable signcryption scheme, in which a message is signcrypted by a signcryptor and only a specific receiver, who called a "designated verifier", verifies it using his own secret key. The scheme is secure, as an adversary can not verify the signature...

  • Algorithmic Complexity of Mathematical Problems: An Overview of Results and Open Problems. CALUDE, CRISTIAN S.; CALUDE, ELENA // International Journal of Unconventional Computing;2013, Vol. 9 Issue 3/4, p327 

    This paper reviews current progress and open problems in algorithmi-cally evaluating the complexity of a large class of mathematical prob-lems/conjectures/ statements.

  • Computability in Europe 2009. Beckmann, Arnold; Merkle, Wolfgang; Löwe, Benedikt // Theory of Computing Systems;Jul2012, Vol. 51 Issue 1, p1 

    No abstract available.

  • On the Solution of the Towers of Hanoi Problem. Ahrabian, Hayedeh; Badamchi, Comfar; Nowzari-Dalini, Abbass // World Academy of Science, Engineering & Technology;Mar2011, Issue 51, p89 

    No abstract available.

  • A neural network--based methodology for the recreation of high-speed impacts on metal armours. Gonzalez-Carrasco, Israel; Garcia-Crespo, Angel; Ruiz-Mezcua, Belen; Lopez-Cuadrado, Jose // Neural Computing & Applications;Feb2012, Vol. 21 Issue 1, p91 

    The prediction of the consequences of a ballistic impact is highly relevant in the advanced material engineering. Traditionally, the solution of this kind of problems was made by means of experimental tests, analytical models or numerical simulations. In this domain, the particularities of the...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics