2021/08/19 by Czerwinski, Reiner
#03D15 #68Q15 #68Q17 #Computational Complexity (cs.CC) #F.2.3 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2108.09269
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.