arXiv:2108.09269cs.CC
Separation of P and NP
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
There have been many attempts to solve the P versus NP problem. However, with a new proof method, P not equal NP can be proved. A time limit is set for an arbitrary Turing machine and an input word is rejected on a timeout. The time limit goes toward infinity. Due to the halting problem, whether a word is accepted can only be determined at runtime. It can be shown by Rice's theorem, if a finite set of words are to be checked, they all have to be tested by brute force.
It's difficult to trust self-published, non-peer reviewed papers on arxiv. You can just as easily find papers claiming P=/=NP https://arxiv.org/abs/2108.09269
dontcontactmeView on HNParent context