Computational complexity has only a little to do with computers, and a great deal to do with decision problems and algorithms. A decision problem consists of a collection of instances, and a yes/no (or true/false) question regarding these instances. A typical decision problem is:
An algorithm is a process for answering the question, given any one of the instances. That is, the same algorithm should correctly solve the question for any of the possible instances. We say an algorithm is efficient or polynomial-time (sometimes shortened to polytime) if it runs in polynomial time with respect to the size of the instance. This characterization is mathematically useful because combinations of efficient algorithms are still efficient. It is also practically useful when the coefficients and exponents of the polynomial are not too large, because such algorithms will fairly quickly produce an answer (or prove that none exists).
There are two aspects to solving any decision problem: Producing an answer (solving the problem), and verifying an answer. Sometimes one of these tasks may be significantly easier than the other. For example, it may be difficult to find a Hamiltonian cycle in a graph, but once we are given a cycle it is straightforward to verify whether or not it really is Hamiltonian. Decision problems which can be solved with an efficient algorithm belong to the class P (for polynomial time). Problems for which candidate solutions can be verified with an efficient algorithm belong to the class NP (for nondeterministic polynomial time). "Nondeterministic" refers to the fact that although we may be able to verify a "yes" answer to the question, verifying a "no" answer basically involves solving the problem itself. Thus the algorithm cannot provide an answer (i.e., is not deterministic), but can decide whether an answer works. So, although every decision problem which can be solved in polynomial time can also be verified in polynomial time, the converse may not be true. Said another way, P is a subset of NP, but it is not known whether the two classes are equal.
Most researchers believe that P <> NP because of the inherent asymmetry between verifying solutions and producing them. For example, verifying the claim that a particular graph has no Hamiltonian cycle often appears to require searching through every possibility unless the graph has some special property (or properties) which guarantee or exclude the existence of a Hamiltonian cycle (or otherwise simplify our search), and we can check in polynomial time whether or not a graph has that property. Thus, verifying a negative answer is tantamount to solving the problem in the first place (exhaustive searches can take a long time). In contrast, verifying whether a given set of edges really is a Hamiltonian cycle in the graph is easy.
One important area of research involves determining whether a problem is in P or NP. Proving a problem is in P is fairly straightforward: Either produce a polynomial time algorithm for solving it, or else find a polynomial time transformation of it into another problem which is already known to be in P. Because adding and multiplying polynomials results in another polynomial, such transformations do not destroy the polynomial time complexity of the algorithm. When there are polynomial time transformations from each problem to the other, we say the problems are (polynomial-time) equivalent to each other.
Proving a problem is not in P is usually not as simple. After all, the inability to find an efficient algorithm does not imply no such algorithm exists. However, there is a third class of decision problems which play a very important role in this paper, namely the class of NPC (NP-complete) problems. These problems are in a sense "the hardest problems in NP," because every problem in NP can be transformed (in polynomial time) to one of them. More generally, a problem which is at least as hard as every problem in NP (but not necessarily in NP) is called NP-hard. Thus, the NP-complete problems are precisely those problems which are both in NP and NP-hard.
In order to show a problem is NP-complete, it suffices to find a polynomial time transformation from an existing NP-complete problem to it. Of course, this requires an NP-complete problem to begin with, and it is not trivial to show that one exists. However, Cook (who introduced the notion of NP-completeness) proved that the satisfiability problem of propositional logic is in fact, NP-complete. Briefly, this problem concerns elements from logic:
A Boolean formula is in conjuctive normal form when it is purely a conjunction of clauses (that is, the formula is true if and only if all of its clauses are true). Then the satisfiability problem (SAT) is:
Since the introduction of NP-completeness, literally hundreds of problems have been proven NP-complete by transforming known NP-complete problems into them. But, for every problem whose computational complexity is determined, it seems two (or more) problems whose computational complexity is unknown are found.
The two problems with which this paper is mostly concerned are the Even Cycle Problem for directed graphs (EVCY) and the square L-matrix problem (LMAT). These two problems are equivalent, but their complexity remains unknown.