NP-complete and PSPACE problems

NP-complete and PSPACE problems
Student’s name
Institution Affiliation(s)

Discuss designing algorithms for NP-complete and PSPACE problems.
NP-complete problem is described in the theory of computational complexity. A problem
is said to be NP-complete if it can be explained by the use of a limited class of brute force search
algorithms. Also, an NP-complete problem can be used to trigger any other problem with the
same algorithm. Each input to the NP-complete problem is associated with a number of solutions
of a polynomial length whose validity can be tested in polynomial time. If the set of solution is
non-empty, then any input will give a “yes” output, and the output will be no if the input is
empty. NP-complete problems are nondeterministic polynomial time problems (Traversa,
Ramella, Bonani, & Ventra, 2015).
PSPACE-complete problem is described in the theory of computational complexity. A
problem is said to be PSPACE-complete if it can be explained by using a given amount of
memory that is polynomial space, i.e. polynomial in the input length. Also, a PSPACE-complete
problem can be used to solve every other similar problem that occupies the same polynomial
space (Traversa et al., 2015).
Examples of NP-Complete problems are Clique, Partition and triangles, 3D-coloring and
Hamiltonian cycle. Basically, the idea promoted by NP-complete asserts that if an efficient
algorithm can be developed for one problem, it can also be developed for other complicated
problems too. Thus to simplify, P defines the type or the category of the problem that comes with
an efficient solution whereas, NP defines a group of problems, each of which has an efficient
recognizable solution. By saying P = NP, we mean to say that for any problem that has an
efficient verifiable solution, we can efficiently identify that solution. However, there are many
scientists who believed that P ≠ NP and defined it as an inability to find the solution efficiently
(Andersen, Flamm, Merkle, & Stadler, 2012).

Figure 1: Flowchart showing NP-Complete problems (Source: Lucas, 2014)
A problem S is NP-hard if every problem in NP is polynomial time reducible to S. S is
NP-hard if, for every S ∈ NP, S, hence implying that S is ‘as hard as’ all the problems in NP
while a problem S is NP-complete if it is NP-hard and it is also in the class NP itself. In symbols,
S is NP-complete if S is NP-hard and S ∈ NP. NP-complete problem forms a set of problems that
could be intractable or tractable (Wuon et al., 2014).
To show that a problem X is NP-complete, first, you indicate that X is NP and then
choose a recognized NP-complete problem. You then create an algorithm that solves Z when
given an algorithm that solves X. We then prove the accuracy of the algorithm. We then conclude
that as the algorithm executes polynomially, Z<X. because Z is NP-complete, X is NP-Hard, and
because X is in NP, X it then NP-Complete.