Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $P(a,b)$ be a class of well-defined problems depending on two parameters. That is, for each pair $(a,b)$ there is a unique solution to problem $P(a,b)$. For example, $a,b$ could be integers, and $P(a,b)$ some number theoretic problem, like finding the largest prime factor of $a+b$.

My question is: Does it make sense to state a theorem aking to

Thm. There exists an algorithm that solves $P(a,b)$ in time $O((ab)^2)$.

I would object that there is always an algorithm which solves $P(a,b)$ in constant time. Namely the algorithm "print the unique solution". I'm asking this question because I found this formulation in a paper on integer programming. The authors describe an algorithm, and then make this statement. The proof is "Take our above algorithm". I was wondering if they should have formulated the theorem differently, like

Thm. Algorithm X solves $P(a,b)$ in time $O((ab)^2)$.

share|cite|improve this question
It would seem that we have finally solved $P = NP$ – Cocopuffs Apr 8 '13 at 11:32
That is my point, indeed. There is an algorithm that prints the correct solution to P ?= NP. It is either of "print P=NP", or "print P!=NP". My question is: Does this make the statement in the first theorem non-sensical, or useless. – Thomas Apr 8 '13 at 11:34
@Thomas: You need to formalise your computation methods. If you want to have 'print the solution' then you first need a way of putting the solution in your computer's memory, or (if your computer is silly enough to have all possible solutions pre-set in its memory) selecting the right one. – Clive Newstead Apr 8 '13 at 11:45
@Thomas: I think the conversation has changed from "there exists an algorithm satisfying this given time constraint" to "there exists an algorithm". Given a particular computational model, you can argue without having your hands on an algorithm that if an algorithm exists then it must take at least [some amount of time] to complete. I'm saying that "print the solution" is not a one-step algorithm when working with any conventional model of computation (say Turing machines), and that it abbreviates a longer algorithm which will, in general, take more time. – Clive Newstead Apr 8 '13 at 11:58
I think the crux of the issue is uniformity. Of course there is an algorithm for each $(a, b)$ that solves the problem $P(a, b)$ in $O(1)$; the real problem is, does there exist one algorithm that solves $P(a, b)$ for all $(a, b)$? – Zhen Lin Apr 8 '13 at 12:45
up vote 8 down vote accepted

I think your difficulty arises from confusing a problem with an instance of a problem. The square root problem is: For a given non-negative integer $N$, calculate the largest integer $s$ such that $s^2 \le N$. A particular value of $N$ defines an instance of the problem.

Now it is true that for a particular given $N$ there is a constant-time algorithm to solve that instance of the problem. For example, when $N=173$, the algorithm is simply to print 13 on the output tape and halt. But that does not mean that the problem can be solved in constant time, because the problem contains many instances. To solve the problem, you have to provide a single algorithm to produce the square root for any $N$.

Any problem with only a single instance is trivial. As you observe, there is a turing machine which halts and prints the answer in constant time. Any problem with only a single instance is trivial in this way, including the $P=NP$ problem. Yes, there is a constant-time algorithm to solve the question of whether $P=NP$. (We just don't know yet what it is.)

However, the problem you describe is not like this. It has many instances, parameterized by $a$ and $b$. Any single instance is easily solved by a single trivial constant-time algorithm. But the entire problem isn't because the entire problem requires a solution for given $a$ and $b$.

The trivial algorithms to solve the single instances by printing single numbers don't solve the entire problem because, given $a$ and $b$, you still need to figure out which trivial algorithm is the correct one, and this is decidedly nontrivial—in fact it's the entirety of the problem.

share|cite|improve this answer
This is a great answer, thanks. I understood two things now: 1) It's about quantifiers: "There exists an algorithm such that for all instances ..." 2) Any problem with only finitely many instances is 'vulnerable' to the "print the solution" algorithm. (In the Turing machine model with finitely many states) – Thomas Apr 8 '13 at 13:03
"Any problem with only a single instance is trivial" should probably be changed to "Any problem with a constant number of instances is trivial" since the time complexity would be bounded by the time taken for the "worst" instance(which is O(1) since it is fixed). – Bakuriu Apr 8 '13 at 15:56

Theorem. Algorithm $X$ described above solves $P(a,b)$ in time $O((ab)^2)$.

Corollary. There exists an algorithm $X$ that solves $P(a,b)$ in time $O((ab)^2)$.

Trivial remark. For each pair $(a,b)$, there exists an algorithm $X_{a,b}$ that solves $P(a,b)$ in time $O(1)$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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