3
$\begingroup$

I am teaching algorithms and theory of computation this semester and had the opportunity to dig a bit into the details of one way functions and the P vs NP problem.

This problem has resisted attacks for a long time now and few experts seem to be hopeful for a resolution soon. Some speculate that it may be independent of our usual axiomatic systems or that its proof may be irreducibly large in some sense---although as a "purer" mathematician I think it is too soon to be developing such feelings.

But given those sentiments from the grapevine, I am wondering about papers of the following form: here is a "plausible" axiom X such that assuming ZF(C)+X, prove the (in)equality---or lean significantly towards one of the possibilities than with ZF(C) alone (When I say "plausible", I only mean that the authors at least consider it somewhat plausible.).

I am not an expert in the area, so please bear that in mind: I only have a dilletante's idea of the literature coming from a couple of surveys (mainly Aaronson's survey and references therein). In particular, a core theme in that survey is the various "barriers" to straightforward reductions, so I am wondering if anyone has found an axiom addressing those barriers or uniting them under a common theme.

Thanks for your time!

Improve this question
$\endgroup$
4
  • 6
    $\begingroup$ No plausible extension of ZFC by any axioms (except for obvious complexity-theoretic axioms such as $\mathrm{P\ne NP}$ itself) is known to resolve the P vs. NP question. At this point, there is no reason to think that any strong axioms should help: the bulk of contemporary computational complexity can be formalized in one way or another in weak fragments of bounded arithmetic, in particular $\mathrm{APC}_2$, and it’s plausible that when $\mathrm{P\ne NP}$ will be finally proven, it will be formalizable in a weak theory of arithmetic as well. $\endgroup$
    – Emil Jeřábek
    Commented Nov 18 at 10:03
  • $\begingroup$ Thanks for the feedback, @EmilJeřábek! I am not sure I understand the intuition though, so remind me: is there a reduction theorem that says if a statement can be formalized in $APC_2$ and a proof of the statement exists (say, in ZFC), then a proof can be also be given in a much weaker system? I recall a theorem of that kind but I cannot pinpoint it. $\endgroup$
    – ode
    Commented Nov 23 at 10:38
  • 1
    $\begingroup$ No, not really, no such thing is true in general. A theory of higher proof-theoretic strength always proves more universal theorems than a weaker one (e.g., consistency statements). It is only an empirical observation that much of the usual results of complexity theory can be formalized in weak fragments of arithmetic. Also, APC2 is the “much weaker system”, so if it’s already formalizable in APC2, you are done. $\endgroup$
    – Emil Jeřábek
    Commented Nov 23 at 11:18
  • $\begingroup$ Thank you again! $\endgroup$
    – ode
    Commented Nov 28 at 9:52

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .