Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: Solving problems by mapping to other problems that we know how to solve

news.ycombinator.com

Post reply on HN
Print view View original

11–20 of 81 posts

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#11

Post by mathcass »

mgraczyk wrote: post #5

This isn't a complete answer to your question, because it's generally more theoretical than operational, but the thing you're describing is often called "reduction": https://en.wikipedia.org/wiki/Reduction_(complexity) In practice, there are many cases where people use SAT solvers for other problems. For some examples: http://homepages.math.uic.edu/~jan/mcs401/reductions.pdf

I came here to upvote this and add on some more resources. (I read the main comment and literally thought "reductions.")

John Langford of Microsoft Research (and formerly of Yahoo! Research) has some some extensive theoretical and practical work here. In particular as they apply to machine learning problems. Check out his page on this[1]. I'd also recommend checking out Vowpal Wabbit[2] which is essentially a working implementation of many of these reductions in ML.

1. https://hunch.net/~jl/projects/reductions/reductions.html

2. https://vowpalwabbit.org/

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#13

Post by tsumnia »

Soloway's work [1] might speak to you. In essence, Soloway referred to this association as "templates", in which we associate problems with those we've seen in the past. While the linked study points at it as a potential negative, you aren't far off in assuming its beneficial as well. When I teach Data Structures and AI courses, I refer it the phenomena as "neutralizing the problem" (borrowed for my years training martial arts). Again, the idea is to model the problem as something we've something seen before - because then, we have solutions for it! The biggest issue is knowing how to best model the problems so that we're not trying to shoehorn everything into a particularly inefficient solution. However, this is a "fun" bit of research, seeing which models best work with which problems.

[1] https://ieeexplore.ieee.org/iel5/32/5010265/05010283.pdf

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#14

Post by logicallee »

I studied machine learning and AI, I think it would be relevant for you to look at Transfer Learning - https://en.wikipedia.org/wiki/Transfer_learning

(By the way if anyone is looking for a Software Engineering Manager in New York City with a specialization in AI, see my profile and get in touch!)

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#15

Post by jonbaer »

This was done (somewhat) a while back with linguistics in the form of symbolic reduction, while it has no direct interpretation to code it could be used that way (or at least I saw it that way), either way I found it to be one of the more interesting ideas in AIML at the time when we were developing the spec, but I don't take credit for it. It is somewhat explained at https://medium.com/pandorabots-blog/aiml-tutorial-the-srai-t... ... all these tags are just wrappers around an execution graph but it was a neat way to filter your way down to a static answer. I tend to think about it when I read https://en.wikipedia.org/wiki/The_Master_Algorithm and his thinking behind Markov logic networks ... YMMV

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#16

Post by srcreigh »

This is the general concept of math: to prove one set contains another set. In some cases you prove set equality by showing each side contains the other.

A simple example of this is: all even integers are divisible by two. That's two sets: the set of even numbers and the set of numbers divisible by two. For any x that is an even number, it is equal to 2k for some integer k. This implies that x/2 = 2k/2 = k. Since x/2 is an integer, it is divisible by 2 QED.

It is also possible to prove that if an integer is divisible by 2, it is even. That's a different proof.

The fact that you can solve problem A in terms of problem B doesn't always mean you can solve problem B in terms of problem A. Just because great minds think alike, doesn't mean people who think alike are great minds.

All problems reducing to other problems in the technical sense are built on such foundations.

The specific area you're thinking of is theoretical computer science.

You might like the textbook "Introduction to the theory of computation" by sipser. It starts by showing the mutual-problem-reducibility of regular languages (AKA the language of deteinistic finite automata / regular expressions) and moves step by step into Turing machines which support general purpose programming languages. And beyond (languages which can only be conputed by hypothetical machines which we don't know how to build in reality.)

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#20

Post by jonnydubowsky »

I’ve wondered the same thing as i run into environmental management problems that seem to fit this model. Work being done with Network Operads, and process calculus is applicable to this line of thought.

This is an accessible paper on the general concepts:

https://arxiv.org/pdf/2101.11115.pdf

Abstract: “We solve complex problems by separating them into manageable parts [2,86]. Human designers do this intuitively, but details can quickly overwhelm intuition. Multiple aspects of a problem may lead to distinct decompositions and complementary models of a system– e.g. competing considerations for cyberphysical systems [63,87]–or simulation of behavior at many levels of fidelity–e.g. in modeling and simulation [88]–leading to a spectrum of models which are challenging to align. We argue that operads, formal tools developed to compose geometric and algebraic objects, are uniquely suited to separate complex systems into manageable parts and maintain alignment across complementary models”

John Baez has some inspiring work in this area as well.

Network Models is a good paper particularly on Network Operads

https://arxiv.org/abs/1711.00037

Post reply on HN