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.

  • 2
    $\begingroup$ It's not clear how to formalize "the algorithm can't solve an easier problem". $\endgroup$ Jun 30 at 3:35
  • 1
    $\begingroup$ 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? $\endgroup$
    – none
    Jun 30 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.