I was reading this paper http://citeseerx.ist.psu.edu/viewdoc/download?doi= in which the author describes an algorithm, based on Groebner basis, whose input is a proposition in Peano arithmetic that satisfies a specific quantifier structure, and the output is True or False. If the output is true, then the proposition must be true. However, sometimes the output is false but the proposition is true, so the algorithm is not a decision procedure for Peano arithmetic -I already know that such an algorithm cannot exist, by Matiyasevich theorem-.

I have two questions:

1: Are there any similar results to this, i.e. an efficient pseudo-decision procedure such that if the output is true, then the proposition must be true, but we cannot say anything in the other case?

2: Is there a chance to use similar ideas to the ones in the paper so that we can overcome the limitations on the quantifier structure of the input propositions, and ask things like "There are many infinitely many prime numbers"?

  • 3
    $\begingroup$ Unfortunately, I know a real efficient constant time such algorithm. The problem is to find one that does something adequately useful. It is also unclear how far "adequate" can be realized. $\endgroup$ – The Masked Avenger Jun 21 '15 at 23:03
  • $\begingroup$ I don't think you have understood my question. $\endgroup$ – Roger Platt Jun 21 '15 at 23:18
  • 2
    $\begingroup$ Then perhaps, Roger, the onus is on you to do a better job of explaining your question. $\endgroup$ – Gerry Myerson Jun 21 '15 at 23:24
  • 1
    $\begingroup$ For any theory in which one believes, say, ZFC plus large cardinals or whatever, then one can search for short proofs of arithmetic statements, saying "true" only when such is found; and saying "false" if a proof of the negation is found or if one has exceeded a fixed time bound. This algorithm does not depend on the quantifier complexity of the given statement, but only on the length of the proof and whether it is shorter than the pre-fixed bound. $\endgroup$ – Joel David Hamkins Jun 22 '15 at 2:10

I don't know anything about (2), but let me try to address (1):

Given a decision problem $P$, let's say a Turing machine $\Phi$ is a pseudo-solver for $P$ if for every $n$, $\Phi(n)$ halts implies $P(n)\iff\Phi(n)=1$. (Note that the algorithm you describe can be thought of as a pseudo-solver, by replacing "outputs "FALSE"" with "goes into an endless loop.") Now, as The Masked Avenger says, the Turing machine which never halts is of course a pseudo-solver for every problem, so that's not really what we're interested in.

That is, we might want to ask:

For which decision problems is there a pseudo-solver $\Phi$ such that (1) $\Phi$ runs efficiently, and (2) $\Phi$ halts frequently?

For example, look at algorithms which halt on a set of asymptotic density 1 - this yields generic computability. We could also allow pseudo-solvers to make (rare) errors - demanding correct halting on a set of density 1 yields coarse computability - or look at other variations; see http://arxiv.org/pdf/1406.2982.pdf for a survey of these.

Lots of decision problems which are complex (or unsolvable) according to the usual model are generically/coarsely/similarly computable in very efficient time - for example, the word problem for Boon's original example of a group with undecidable word problem is generically decidable in linear time.


1) A positive result: Mathematica's FindInstance provides a good pseudo-decision procedure for most existential or universal questions, e.g. $$\mathtt{FindInstance[ x^2 - 3y^2 == 1 \ \&\& \ 10 < x < 100,\{x,y\}, Integers]}.$$ It can accept inputs of nested quantifiers also.

2) A negative result: The theory $I\Delta_0$, which proves the totality of all polynomial-growth functions, is not known to prove the infinitude of primes. At least, no one has found such a proof since 1988, when Paris, Wilkie and Woods proved the infinitude of primes from $I\Delta_0 + $ "the function $x \rightarrow x^{\log_2(x)}$ is total".

So, extrapolating unrigorously, any algorithm now for deciding the infinitude of primes probably can also decide the totality of some non-polynomial-growth functions, and probably isn't efficient in the usual polynomial-time sense. Good algorithms may only be able to decide simpler results.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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