1 citations · 1 across the 3 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2019
Case Study of the Proof of Cook's theorem - Interpretation of A(w)
Yu Li
Cook's theorem is commonly expressed such as any polynomial time-verifiable problem can be reduced to the SAT problem. The proof of Cook's theorem consists in constructing a propos…
cs.CC2019★ 1 cited
Interpretation of NDTM in the definition of NP
JianMing Zhou, Yu Li
In this paper, we interpret NDTM (NonDeterministic Turing Machine) used to define NP by tracing to the source of NP. Originally NP was defined as the class of problems solvable in…