Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In combinatorics, one can sometimes get an algorithmic proof, which loosely has the following form:

-The proof moves through stages

-An invariant is shown to hold by induction from previous stages

-The algorithm is shown to terminate

-The invariant holding at termination implies the desired claim.

Perhaps the best example I know of is an algorithmic proof of Konig's theorem, which in a sense is just a max-flow/min-cut algorithm. In some sense, most induction proofs fit this mold.

The above example runs in polynomial time. Are there good examples of algorithmic/induction proofs that take super-polynomial time to prove things that don't obviously need such induction?

That is, I don't want Ackermann-like recurrences, or anything that is "brute-force". Further, I'm not looking for super-polynomial time algorithms that solve instances of problems, but rather am looking for super-polynomial time algorithms that prove a theorem of some sort (eg. like a combinatorial max-min theorem in the above example).

share|improve this question

3 Answers 3

The standard proofs of Sperner's Lemma are the first thing that comes to my mind in this context. They don't have exactly the form you mentioned; in particular they're not really inductive. Nonetheless, the proofs use a path-following algorithm which may take exponential time but is guaranteed to terminate for combinatorial reasons.

In fact the complexity class PPAD is defined as those problems for which such a path-following argument proves existence, and "SPERNER" is a PPAD-complete problem. It is an open problem whether such problems can be solved in polynomial time (I think most people guess not). Furthermore just by definition all the other PPAD-complete problems (or PPAD problems in general) have the form you want, i.e. and algorithmic existence proof.

There are a number of other such complexity classes defined in terms of types of non-polynomial-time existence proofs. Examples are PPA, PLS, etc. See Papadimitriou's paper "On the complexity of the parity argument and other inefficient proofs of existence" for more examples.

share|improve this answer
    
Thanks, I am aware of Papadimitriou's various inefficient proofs of existence, but I consider these more of a brute-force type of proof in the sense that the algorithms themselves don't really establish the existence of the desired object - it is the various lemmas (parity, etc) that he uses to establish the existence. The algorithms sort of fall out in a trivial way. Though, perhaps it isn't a meaningful distinction. –  miforbes Jul 31 '10 at 14:31

I agree with Noah that Papadimitrou's classification of several cannonical types of algoritmic proofs is very relevant to the question and to the understanding the computational complexity of mathematical existence proofs.

Another interesting class is described by finding the sink in acyclic unique sink orientations (AUSO) of the didcrete n dimensional cube. Those are orientations of the discrete cube so that every face has a unique sink. There is an algorithm to find the sink in $exp (\sqrt n )$ steps.

Another algorithmic proof whose complexity is unknown is Barany's proof of colored caratheodory theorem.

share|improve this answer

The Hydra game:

I'm not sure if that counts as an "Ackermann-like recurrence" but the algorithm is super-duper-exponential and then some. It's not even possible to write down a formula for the running time, but it definitely terminates.

share|improve this answer

Your Answer

 
discard

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.