The complexity of natural extensions of efficiently solvable problems
Andrei Lapets · 2010
A problem is in the class NP when it is possible to compute in polynomial time that a given solution corresponds to a given problem instance. Those problems for which it is possible to compute in polynomial time a solution for any problem instance are also in the class P. We consider a natural conjunction operation for problems that can be computed in polynomial time. We introduce the notion of an abundant problem in P, and specify conditions under which the conjunction of two abundant problems in P produces a problem that is NP-complete. We discuss how this is related to multi-dimensional variants of common, efficiently computable graph problems. 1 Common Definitions and Conventions Definition 1.1. We define a problem to be any Turing machine