ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let ff be a polynomial-time algorithm, viewed as a function symbol of PV\mathsf{PV}, and let

φP=NP(f):=∀x ∀y [ψSAT(x,y)→ψSAT(x,f(x))]\varphi_{\mathsf{P} = \mathsf{NP}}(f):= \forall x\,\forall y\,[\psi_{\mathsf{SAT}}(x,y) \rightarrow \psi_{\mathsf{SAT}}(x,f(x))]

where ψSAT(x,y)\psi_{\mathsf{SAT}}(x,y) expresses that yy satisfies the Boolean formula encoded by xx. Unprovability conjecture. For no polynomial-time algorithm ff does theory PV\mathsf{PV} prove the sentence φP=NP(f)\varphi_{\mathsf{P} = \mathsf{NP}}(f). This is a formal weakening of the conjecture that P≠NP\mathsf{P} \neq \mathsf{NP}: if P=NP\mathsf{P} = \mathsf{NP}, the equality should nevertheless not be provable using only polynomial-time concepts and reasoning. By standard conservation results, the claim is also equivalent to consistency of PV\mathsf{PV} and S21\mathsf{S}^1_2 with P≠NP\mathsf{P} \neq \mathsf{NP} in the intended sense.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.