A Study on Designing Algorithms for NP-complete and PSPACE Problems

This assignment delves into the realm of NP-complete and PSPACE problems within the framework of computational complexity theory. It elucidates the characteristics of NP-complete problems, which can be addressed using brute-force search algorithms and are reducible to other problems. The assignment further explains PSPACE-complete problems, which are defined by their memory usage in polynomial space. It provides examples of NP-complete problems such as Clique, Partition, 3D-coloring, and Hamiltonian cycle. The document then clarifies the relationship between P and NP, discussing the implications of P=NP and P≠NP. The assignment also covers NP-hard and NP-complete problems, explaining the reduction process and offering algorithms for Graph coloring, Knapsack, and Travelling Salesman problems. The document concludes with references to the sources used.

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.

Example #1: Graph coloring algorithm
Figure 2: Python code for a graph coloring algorithm (Source: Lucas, 2014)
Example #2: The Knapsack problem
Figure 3: Pseudocode algorithm for solving the Knapsack problem (Source: Lucas, 2014)

Example #3: The Travelling Salesman problem
Figure 4: Travelling salesman problem (Source: Andersen et al., 2012)
The problem is finding the shortest possible route between four interconnected cities.

References
Andersen, J. L., Flamm, C., Merkle, D., & Stadler, P. F. (2012). Maximizing output and
recognizing autocatalysis in chemical reaction networks is NP-complete. Journal of
Systems Chemistry, 3(1), 1. https://doi.org/10.1186/1759-2208-3-1
Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in Physics, 2.
https://doi.org/10.3389/fphy.2014.00005
Traversa, F. L., Ramella, C., Bonani, F., & Ventra, M. D. (2015). Memcomputing NP-complete
problems in polynomial time using polynomial resources and collective states. Science
Advances, 1(6), e1500031. https://doi.org/10.1126/sciadv.1500031
Wuon, K., García de Abajo, J., Soci, C., Ping Shum, P., & Zheludev, N. I. (2014). An optical
fiber network oracle for NP-complete problems. Light: Science & Applications, 3(2),
e147. https://doi.org/10.1038/lsa.2014.28