The complexity of natural extensions of efficiently solvable problems
OA Version
Citation
Lapets, Andrei. "The complexity of natural extensions of efficiently solvable problems", Technical Report BUCS-TR-2010-005, Computer Science Department, Boston University, March 15, 2010. [Available from: http://hdl.handle.net/2144/3784]
Abstract
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.