Title: The complexity of natural extensions of efficiently solvable problems

Author: Andrei Lapets

Date: March 15, 2010

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.