2

For a decision problem, if a mathematician finds a simple polynomial time procedure that solves it, does it mean that the problem is polynomial time solvable?

For example, consider a decision problem: whether there exists a vector $(x_1, x_2, ..., x_K)$ such that $f(x_1, x_2, ..., x_K, d, M, N)=0$, where $d, M, N$ are parameters, and $f$ is a given function.

Suppose that a mathematician proves that the answer is yes iff $M+N \geq d(K+1)$. Then, can we say that the decision problem is polynomial time solvable?

If so, then I would be puzzled by another example I could think of, which involves Fermat's Last Theorem. We can pose the theorem as a question decision problem: whether we can find positive integers $a,b,c$ such that $a^n + b^n = c^n$ for a given positive integer $n$. The size of the problem is $n$. The problem was solved by mathematician Wiles in 1997: the answer is yes if $n=1$ or $2$, and is no otherwise. This answer can be easily written as a line of code in a regular computer (or a very simple program in a Turing Machine), and the time complexity is certainly polynomial. So can we say that a Turing Machine can solve Fermat's Last Theorem in polynomial time (actually constant time), even though it took mathematicians centuries to solve it?

Leon
  • 21
  • Depends on what you mean by 'simple procedure'. – copper.hat Aug 28 '13 at 23:01
  • I'd say it depends what you mean by "solve". – dfeuer Aug 28 '13 at 23:01
  • 1
    We certainly cannot "say that a Turing machine can solve Fermat's Last Theorem in polynomial time"; well, we can say it but not if we want to make sense. In the first place, theorems cannot be "solved"; problems can be solved. In the second place, "polynomial time" makes sense only when one has specified what constitutes an instance of the problem and what is the size of an instance. – Andreas Blass Aug 28 '13 at 23:10
  • 4
    The truth-table algorithm for deciding satisfiability of formulas in propositional logic is "a simple procedure" under any plausible definition of "simple" that I can think of (and the proof of its correctness is simple too). Yet it takes exponential time, no polynomial time algorithm is known, and most experts believe that no polynomial time algorithm exists for this problem. – Andreas Blass Aug 28 '13 at 23:13
  • Hi Copper.hat, simple means polynomial time. Just updated. – Leon Aug 28 '13 at 23:41
  • dfeuer, "solve" means giving a correct to the decision problem posed for the Fermat's Last Theorem. – Leon Aug 28 '13 at 23:44
  • Andreas, I posed the Fermat's Last Theorem as a decision problem so that proving the theorem is equivalent to answering the decision problem. An instance of the problem corresponds to a particular value of $n$, and the size of the problem is $n$. – Leon Aug 28 '13 at 23:47

1 Answers1

0

I think there's some confusion about terminology, as copper.hat and dfeuer point out.

Let's define a problem to be sets $I,O$ of inputs and outputs, together with a function $P:I\to O$ which defines the unique correct output for a given input. We assume elements of $I$ can be measured (by the number of bits $n$ they are encoded in, say) in some way. Then we can say the problem $(I,O,P)$ is polynomial time solvable is there exists a Turing machine which can process $i\in I$ in a number of operations at most polynomial in $n$ and leave $P(i)$ on the tape.

In other words, a problem is polynomial time solvable if some genius could invent a Turing machine which responds correctly to every possible input quickly enough.

The key thing here is what are the range of inputs?

Yes, if a civilization of mathematicians spends a thousand years developing the machinery to prove that $P(1) = P(2) = \text{yes}$ and $P(i) = \text{no}$ otherwise, then the decision problem "Is there an interesting solution to $a^i + b^i = c^i$?" taking $i \in\{1,2,\ldots\}$ to $\{\text{yes},\text{no}\}$ is polynomial time solvable. Very trivially.

By contrast, the decision problem "Is there an interesting solution to the formula $i$?" where $i\in I$ is an arbitrary problem which is specified as input, then you're probably not going to get a simple solution! (See the Boolean case mentioned by Andreas Blass for example).

not all wrong
  • 16,178
  • 2
  • 35
  • 57
  • So however 'powerful' a Turing Machine is, it is still designed by a human being. To solve a problem using a Turing Machine, a human being needs to design the Turing Machine in the first place. I feel that it is misleading to describe the complexity of a problem by the time complexity of a Turing Machine. We should also consider the complexity of inventing the Turing Machine. – Leon Aug 29 '13 at 15:53
  • To be fair, we can force a Turing Machine to do the proof that a mathematician has gone through. As usual, a Turing Machine solves a problem by testing whether the input belongs to a language. But we can define a language as follows: \begin{equation} L={i | i\in N^+, \mathrm{~and~there~exist~} a, b, c \in N^+ \mathrm{~such~ that~} a^i+b^i=c^i \mathrm{~given~the~knowledge~base~ including~facts~such~as~} 1+1=2, ..., x^2=x\times x, ..., \mathrm{~and~given~the~reasoning~rules~such~as~} A \Rightarrow B \mathrm{~implies~} \bar{B} \Rightarrow \bar{A}, ...} \end{equation} Does it make sense? – Leon Aug 29 '13 at 23:18
  • "I feel that it is misleading..." Well, that's a feeling, and there's not much you can do about it! There is, as far as I am aware, essentially no rigorous way of evaluating the complexity of "how hard it is to think of the solution to a specific problem", much as there is no way to evaluate "the difficulty of solving travelling salesman with this specific set of towns". One can only look at the difficulty of solving a wider class of problem, or a specific instance of the problem. – not all wrong Aug 30 '13 at 10:20