# Are there some algorithms which have high consistency strength?

Are there some algorithms, their time complexity is relatively good, for example polynomial time.

And the correctness of them has high consistency strength.

And these algorithms shouldn't able to solve an easier proplem.

A non-example: assume ZFC+there are infinitely many woodin cardinals. given natural number n, decide whether $$\Pi^1_n$$ determinacy is true.

The algorithm is simply input n and output true. Although its correctness has very high consistency strength, but this algorithm can solve much easier problem.

• It's not clear how to formalize "the algorithm can't solve an easier problem". Jun 30 at 3:35
• Specification: input n, output true. Implementation: if n does not code a proof in T=ZFC+Woodin cardinals that 1=0, output true; else output false. Proof of correctness: algorithm is correct (i.e. it implements the specification) if and only if T is consistent. Running time: should be approximately linear in size of n. Does this count?
– none
Jun 30 at 14:15