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$ Commented Nov 2, 2014 at 9:24
  • $\begingroup$ what textbook ? $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Jun 18, 2018 at 18:13

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.