How should I understand the definition of computational problem?
A computational problem is a mathematical object representing a collection of questions that computers might be able to solve. For example, the problem of factoring
"Given a positive integer n, find a nontrivial prime factor of n."
What is the mathematical object in the example above? Quoting Wikipedia again:
Commonly encountered mathematical objects include numbers, permutations, partitions, matrices, sets, functions, and relations.
So how can you 'represent' a collection of questions with numbers or permutations, matrices etc.? What is meant here is probably the following collection of sentences:
'find a nontrivial prime factor of 1', 'find a nontrivial prime factor of 2' and so on...
But the thing is - these sentences are not mathematical objects.
A little further in the article it reads:
A computational problem can be viewed as an infinite collection of instances together with a solution for every instance.
which makes perfect sense, but I don't quite see the relationship with the first definition.
-
2$\begingroup$ Hint: get a textbook. $\endgroup$Raphael– Raphael2015年10月01日 16:04:28 +00:00Commented Oct 1, 2015 at 16:04
-
$\begingroup$ @Raphael which one do you recommend? $\endgroup$user4205580– user42055802015年10月01日 16:23:03 +00:00Commented Oct 1, 2015 at 16:23
-
$\begingroup$ I don't have experience with English textbooks on computability, sorry. You can check syllabus of introductory university courses. $\endgroup$Raphael– Raphael2015年10月01日 19:56:03 +00:00Commented Oct 1, 2015 at 19:56
-
2$\begingroup$ Sorry, but the answers like "get a textbook" are so unhelpful. Why is it always so elitist in math communities? $\endgroup$avf– avf2020年04月27日 06:56:28 +00:00Commented Apr 27, 2020 at 6:56
3 Answers 3
But the thing is - these sentences are not mathematical objects.
Yes, they are. A set of sentences can be a mathematical object. Just about anything can be a mathematical object.
A computational problem can be viewed as an infinite collection of instances together with a solution for every instance.
[...] but I don't quite see the relationship with the first definition
Well, "an infinite collection of instances together with a solution for every instance" is a mathematical object (representing a collection of questions that computers might be able to solve).
The mathematical object is "a collection of questions". A "collection" is another word for a "set". You listed sets as one kind of mathematical object.
The connection between the two definitions is: each instance represents a slightly different question that a computer might be able to solve. So, you have one instance per question.
A sentence can be a mathematical object, but it isn't very helpful in your case. One way to approach the answer would be to analytically decompose the problem into simple and familiar mathematical objects and then to build a more complex mathematical object representing your problem. So:
"Given a positive integer n, find a nontrivial prime factor of n."
- You can salvage $n$ - a familiar mathematical object, an integer.
- Investigating further, you can salvage $p$ - a prime factor of $n$.
- The question establishes a relation between $n$ and $p,ドル restated using Greek and Hebrew of mathematics: $R = \{(n, p) \;|\; \forall q \in (\mathbb{N} \setminus \{1, p\}): (p \div q) \not \in \mathbb{N} \land \exists m \in \mathbb{N}: p \cdot m = n \},ドル which is a relation, a familiar mathematical object, further written as $n R p$.
- Now it's time to state the problem. For example, you could use the language of first order logic to formulate it: $p \impliedby n R p$. The logical interpretation of such formula is "if $p$ is a non-trivial prime factor of $n,ドル then $p$. Computational interpretation of this formula is "find all $p$ which are non-trivial factors of $n$".
Finally, you can go one step further and implement it in a programming language, for example, in Prolog:
prime_factor_of_n(P, N) :- M in 2..N, P is N / M, prime(P).