Mathematics was developed as a strong research instrument with fully verifiable argumentations.
We call any consistent and sufficiently powerful formal theory that enables to algorithmically
verify for any given text whether it is a proof or not algorithmically verifiable mathematics
(AV-mathematics for short). We say that a decision problem L ⊆ Σ ∗ is almost everywhere
solvable if for all but finitely many inputs x ∈ Σ ∗ one can prove either “x ∈ L” or “x 6∈ L” in
AV-mathematics.
First, we prove Rice’s theorem for unprovability, claiming that each nontrivial semantic prob-
lem about programs is not almost everywhere solvable in AV-mathematics. Using this, we show
that there are infinitely many algorithms (programs that are provably algorithms) for which there
do not exist proofs that they work in polynomial time or that they do not work in polynomial
time.
Note that, if P = NP is provable in AV-mathematics, then for each algorithm A it is provable
that “A does not solve SATISFIABILITY or A does not work in polynomial time.” Interestingly,
we show that there exist algorithms for which it is neither provable that they do not work in
polynomial time, nor that they do not solve SATISFIABILITY. Moreover, there is an algorithm
solving SATISFIABILITY for which one cannot prove in AV-mathematics that it does not work
in polynomial time.
Furthermore, we show that P = NP implies the existence of algorithms X for which the
true claim “X solves SATISFIABILITY in polynomial time” is not provable in AV-mathematics.

 Finally, we prove that if P vs. NP is not solvable in AV-mathematics, then P is a
proper subset of NP in the world of complexity classes based on algorithms whose behavior and
complexity can be analyzed in AV-mathematics. On the other hand, if P = NP is provable, we can
construct an algorithm that provably solves SATISFIABILITY almost everywhere in polynomial
time.