Two theorems about the P versus NP problem

2018/04/30 by Tianheng Tsui, Tsui, Tianheng · 1 citation
Computer Science · #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1805.01755

openalex publication_date 2018/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Two theorems about the P versus NP problem be proved in this article (1) There exists a language L, that the statement L ∈ P is independent of ZFC. (2) There exists a language L ∈ NP, for any polynomial time deterministic Turing machine M, we cannot prove L is decidable on M.

Cited by

• A new viewpoint of the G "odel's incompleteness theorem and its\n applications

Related

• Recursively Undecidable Properties of NP
• Separation of P and NP
• A Solution to the P versus NP Problem
• A Proof for P =? NP Problem
• Computability vs. Nondeterministic and P vs. NP