Some simple but interesting results concerning the P ?= NP Problem
Antti Ylikoski · ACM SIGACT News · 2004
In this paper, I discuss some properties of two functions, which I call f1() and f2(), which are interesting from the point of view of the P ?= NP problem. The both functions f1() and f2() concern the problem of solving a nondeterministic polynomial-time problem deterministically in a polynomial time. Based on the results, I finally outline a research program to study the P ?= NP problem.