<p>While there is no formal definition of what constitutes a <em>natural</em> algorithmic problem,
in most cases there is pretty good consensus whether a specific problem is natural or artificial. Natural usually means that the problem is introduced and investigated on its own right, it comes from the &quot;real world,&quot; or at least from some abstraction of that. In contrast, artificial problems are typically created for the mere purpose of illustrating some complexity phenomenon, without independent motivation to investigate the problem on its own.</p>
<p><strong>Question:</strong> is there any algorithmic problem that is on or near the borderline between the two worlds? This would mean a problem that is viewed natural by a (non-negligible) fraction of researchers, but found artificial by another (non-negligible) fraction.</p>
<p><strong>Note.</strong> I could imagine a potential answer along the following lines. Take a natural problem, but translate it into the &quot;wrong&quot; encoding,  that is, an encoding which is not a &quot;natural match&quot; to the problem. For example, encode graphs by positive integers. Then call such an integer <em>Hamiltonian,</em> if it encodes a Hamiltonian graph. For a graph, it is a natural problem whether it is Hamiltonian or not. But the same question is not very natural for an integer; the set of Hamiltonian integers does not seem to be well motivated, it appears rather artificial.</p>
<p>Another example: call a graph <em>prime</em>, if its integer encoding is a prime number. Being prime or not is a natural question for integers. But it seems quite artificial for a graph. From the graph theory point of view, there seems to be no good motivation to study the set of graphs that are encoded by prime numbers.</p>
<p>These examples point out that the particular encoding used for a problem can have a significant impact on its naturalness.</p>

CC BY-SA 4.0
2022-11-04T01:05:43.580Z
*Given a Boolean formula with $n$ variables, can you compute (with probability more than $2/3$) an assignment to the variables that has Hamming distance at most $n/2+O(\sqrt n)$ to some satisfying assignment, if there is one?*  Is that one natural or not?  We need a poll!
Neal Young
CC BY-SA 4.0
2022-11-04T03:05:16.417Z
@NealYoung This problem seems natural to me, since it aims at finding an approximation of a satisfying assignment.
Andras Farago
CC BY-SA 4.0
2022-11-04T12:14:34.453Z
Many problems are studied not because we want to solve them in real life, but because understanding them would help building a general picture of a topic. I'm not sure this fits in your decision of naturalness. To me a definition of "natural" would be broader: the only artificial problems are the ones that don't help us in *any* way, however indirect.
Denis
CC BY-SA 4.0
2022-11-04T22:07:03.917Z
@Denis If we create a problem via diagonalization, just to separate complexity classes, then such a problem is usually viewed artificial. Yet, it is still helps us in some way: it allows to prove complexity class  separation.
Andras Farago
CC BY-SA 4.0
2022-11-04T22:30:42.283Z
@AndrasFarago Complexity and Calculability are somehow special in this respect, as they talk about the existence or non-existence of problems with certain properties. So problems are created just to satisfy these properties, and we call tem "artificial". But in many other fields of TCS, especially the most theoretical ones, some problems are considered interesting without directly modelizing a real-world problem. But I think I see what you're looking for: a problem that could be considered at the same time natural, and artificial in the sense of "created to have some properties".
Denis
<cc.complexity-theory><ds.algorithms><graph-theory><graph-algorithms><nt.number-theory>
On the borderline between natural and artificial problems
Andras Farago
# On the borderline between natural and artificial problems

(Asked by: username_0 on 2022-11-03)

While there is no formal definition of what constitutes a *natural* algorithmic problem,
in most cases there is pretty good consensus whether a specific problem is natural or artificial. Natural usually means that the problem is introduced and investigated on its own right, it comes from the "real world," or at least from some abstraction of that. In contrast, artificial problems are typically created for the mere purpose of illustrating some complexity phenomenon, without independent motivation to investigate the problem on its own.

**Question:** is there any algorithmic problem that is on or near the borderline between the two worlds? This would mean a problem that is viewed natural by a (non-negligible) fraction of researchers, but found artificial by another (non-negligible) fraction.

**Note.** I could imagine a potential answer along the following lines. Take a natural problem, but translate it into the "wrong" encoding, that is, an encoding which is not a "natural match" to the problem. For example, encode graphs by positive integers. Then call such an integer *Hamiltonian,* if it encodes a Hamiltonian graph. For a graph, it is a natural problem whether it is Hamiltonian or not. But the same question is not very natural for an integer; the set of Hamiltonian integers does not seem to be well motivated, it appears rather artificial.

Another example: call a graph *prime*, if its integer encoding is a prime number. Being prime or not is a natural question for integers. But it seems quite artificial for a graph. From the graph theory point of view, there seems to be no good motivation to study the set of graphs that are encoded by prime numbers.

These examples point out that the particular encoding used for a problem can have a significant impact on its naturalness.

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, graph-algorithms, nt.number-theory
> **Comments:**
> **username_1**: *Given a Boolean formula with $n$ variables, can you compute (with probability more than $2/3$) an assignment to the variables that has Hamming distance at most $n/2+O(\sqrt n)$ to some satisfying assignment, if there is one?*  Is that one natural or not?  We need a poll!  
> **username_0**: @NealYoung This problem seems natural to me, since it aims at finding an approximation of a satisfying assignment.  
> **username_2**: Many problems are studied not because we want to solve them in real life, but because understanding them would help building a general picture of a topic. I'm not sure this fits in your decision of naturalness. To me a definition of "natural" would be broader: the only artificial problems are the ones that don't help us in *any* way, however indirect.  
> **username_0**: @Denis If we create a problem via diagonalization, just to separate complexity classes, then such a problem is usually viewed artificial. Yet, it is still helps us in some way: it allows to prove complexity class  separation.  
> **username_2**: @AndrasFarago Complexity and Calculability are somehow special in this respect, as they talk about the existence or non-existence of problems with certain properties. So problems are created just to satisfy these properties, and we call tem "artificial". But in many other fields of TCS, especially the most theoretical ones, some problems are considered interesting without directly modelizing a real-world problem. But I think I see what you're looking for: a problem that could be considered at the same time natural, and artificial in the sense of "created to have some properties".  

---

## 0 answers

