2024/01/15 by Bhupinder Singh Anand, Anand, Bhupinder Singh
Computer Science · #00A30 #03A05 #03B10 #03D10 #03D15 #03F25 #03F30 #68Q15 #68Q17 #68T27 #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.2401.09478
openalex publication_date 2024/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We distinguish finitarily between algorithmic verifiability, and algorithmic computability, to show that Goedel's 'formally' unprovable, but 'numeral-wise' provable, arithmetical proposition [(Ax)R(x)] can be finitarily evidenced as: algorithmically verifiable as 'always' true, but not algorithmically computable as 'always' true. Hence, though [R(x)] is algorithmically verifiable as a tautology, it is not algorithmically computable as a tautology by any Turing machine, whether deterministic or non-deterministic. By interpreting the PvNP problem arithmetically, rather than set-theoretically, we conclude that the clkasses P and NP are not well-defined finitarily since it immediately follows that SAT is neither in P nor in NP.