0
$\begingroup$

  1. In computation theory, when talking about the computability and complexity of a problem, what is the definition of a problem?

    How specific should a problem be? For example, can the followings all be function evaluation problems?

    • evaluate $f$, where $f(x)=x^2, x \in \mathbb R$
    • evaluate any function in $\mathbb R^{\mathbb R}$.
    • evaluate any function in $Y^X$, where $X$ and $Y$ are any two sets.

  2. Without restriction to the computability and complexity of a problem (or even without restriction to computation theory), how is a problem defined?

    Can the above examples in 1 all be function evaluation problems?

Thanks.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Have you looked in a textbook? $\endgroup$
    – Raphael ♦
    Nov 2, 2014 at 9:24
  • $\begingroup$ what textbook ? $\endgroup$
    – Tim
    Nov 2, 2014 at 11:33
  • $\begingroup$ This is a basic definition in complexity; en.wikipedia.org/wiki/… You can also look at every complexity textbook or the famous algorithm design book. For reference, the book "Languages and Autumata" or "Introduction to algorithms" have the definitions. $\endgroup$
    – orezvani
    Nov 3, 2014 at 23:06
  • $\begingroup$ Thanks. @emab. Also appreciate if you could let me know which pages/sections of the two books $\endgroup$
    – Tim
    Nov 3, 2014 at 23:08
  • 1
    $\begingroup$ Introduction to algorithms, 3rd edition p.1054 has a brief formal description of a problem. It borrows the definition from the first book that I referenced. You may look at the book or wikipedia pages for more details. $\endgroup$
    – orezvani
    Nov 3, 2014 at 23:22

2 Answers 2

Reset to default
3
$\begingroup$

A problem is anything you're trying to solve computationally. Problems typically specify an input and a desired output which, for most models of computation, will both be finite. Any statement of the form, "Given $X$, compute/evaluate/find/determine/decide whether/..." is a problem.

So, yes, all the things you describe in the question are problems. (Though, in the case where the input is the uncountable set $\mathbb{R}$, you need to be careful about how you specify what the input is.)

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thanks. (1) In the problem to evaluate any function in $Y^X$, where $X$ and $Y$ are any two sets, is the input space $Y^X$ or $X$ or $Y^X \times X$? Is the output space $Y$? (2) When people talking about computability and complexity of a problem such as P and NP and polynomial complexity for the problem, can the problem vary from being arbitrarily general to arbitrarily specific? $\endgroup$
    – Tim
    Nov 1, 2014 at 23:44
  • $\begingroup$ It depends what you mean by "evaluate any function". For any specific function $f$, "Given $x$, evaluate $f(x)$" is a problem. If you want "Given $f$ and $x$, evaluate $f(x)$" to be a problem, you need to state how $f$ is to be specified as part of the input. I don't know what you mean by "can the problem vary from being arbitrarily general to arbitrarily specific?" $\endgroup$
    – David Richerby
    Nov 1, 2014 at 23:47
  • $\begingroup$ If $f$ is not specified completely but can be any from $Y^X$, is this still a function evaluation problem? Is the set of all the inputs $Y^X$ or $Y^X \times X$ but not $X$? $\endgroup$
    – Tim
    Nov 1, 2014 at 23:50
  • $\begingroup$ I don't know what you mean by $f$ not being specified completely. If something isn't specified, it isn't anything at all and certainly not a problem. If $X$ is an infinite set, then $Y^X$ isn't even countable, so it's very hard to define a problem "Given $f$ and $x$, compute $f(x)$", since you typically can't represent all possible functions $f$ as inputs. $\endgroup$
    – David Richerby
    Nov 2, 2014 at 0:04
  • $\begingroup$ Do you mean that a problem in computation theory must be specific, while a problem can be very general (such as taking $Y^X$ as input) when without restriction to computation theory? $\endgroup$
    – Tim
    Nov 2, 2014 at 0:11
2
$\begingroup$

A computational problem can be viewed as an infinite collection of instances together with a solution for every instance.

For example, consider the problem of finding $f(x)=x^2$. Then $x$ is the input; $<5>$ is an input instance and $25$ is the solution to that. Therefore, This problem is defined by the pairs of input and answer, i.e. $f=\{(1,1), (2,4), (3,9),...\}$.

Note that you should not confuse the problem instance with problem. A problem instance is a given input of a problem; Therefore, a problem is a set of instances and their solutions.

More formally, we encode each possible pair $(instance, solution)$ using an alphabet (usually $\{0,1\}$). The set of such strings is called the language of that problem. Therefore, the problem becomes the membership of a string in that language.

Improve this answer
$\endgroup$
3
  • $\begingroup$ How would this make sense for an undecidable problem if some instances may have no solutions at all? $\endgroup$
    – Carlos Pinzón
    Jun 18, 2018 at 4:18
  • $\begingroup$ @CarlosPinzón If a problem has no solution and does not accept any input, the set is empty (would you call it a problem without input and output?). However, an undecidable problem may have some solutions, but there is no algorithm to find the solutions. So, the definition does work on those. $\endgroup$
    – orezvani
    Jun 18, 2018 at 8:47
  • $\begingroup$ Thanks, I understood the idea of the input-output tuples. Still, let's say your problem is about checking if a given integer is greater than 0. We can not just encode the problem literally as a set of tuples matching each integer x to (x>0) because that set would be infinite, thus making it impossible for any human or machine to read the problem description; also because if we could, then that would be the answer. Instead, we need to formally encode the statement "check if x is greater than 0". How is that done? $\endgroup$
    – Carlos Pinzón
    Jun 18, 2018 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.