Solution of Non-deterministic Problem

This article discusses the solution of non-deterministic problem, which is a type of problem that cannot be solved in polynomial time but can be checked in polynomial time about its correctness. The article covers its background, aims, methodology, expected outcome, timeframe, and references. The research aims to find a specific total bound of subset S for which there will be one unique solution. The total research project is expected to be completed in approximately 11 days.

Running head: Solution of Non-deterministic Problem
Solution of Non-deterministic Problem
Name of the Student
Name of the University
Author Note

1Solution of Non-deterministic Problem
Table of Contents
Background:...............................................................................................................................2
Aims:..........................................................................................................................................2
Methodology:.............................................................................................................................3
Expected outcome:.....................................................................................................................4
Timeframe:.................................................................................................................................4
References:.................................................................................................................................6

2Solution of Non-deterministic Problem
Background:
Non-deterministic polynomial time (NP) problem is a type of problem which cannot
be solved in polynomial time but can be checked in polynomial time about its correctness.
This is unlike the Polynomial time (P) problems that can be checked and solved within
polynomial time (Traversa et al. 2015). The polynomial time is simply the time required to
solve the problem where the time is the polynomial function of the input size to the problem
(Kearns and Pitt 2014). Now, to solve the NP problem often a computer or a Non-
deterministic Turing Machine (NTM) is used that can try out many guessed solutions of the
problem and spot the correct one within polynomial time (Rendell 2016). Now, NP problems
can be either of the type NP-hard or NP-complete. NP-hard are the type of problem which are
the same hard as the hardest problems in NP. Each NP-hard problem may or may not be an
entity of the NP, yet they can be of P type. However, a NP-complete problems are problems
which are the hardest of NP type (Tang et al. 2015). Every entity of an NP-complete problem
must be a NP problem. Now, in this research a particular NP problem is selected and the
procedure with required time to solve each step of the problem is proposed here.
Aims:
The chosen problem is a NP-hard problem which is described as follows. Given, there
are n sets X1,X2,X3…Xn, each containing k non-negative integers. The objective is to select
a subset S from (X1*X2*X3*…Xn) which will contain every element in all the sets and the
minimum bound of S will be either less than or equals to the sum of individual bounds of
X1,X2,…Xn. The bound is simply the sum of the elements in a set. Additionally, the research
aims to find a specific total bound of subset S for which there will be one unique solution.

3Solution of Non-deterministic Problem
Methodology:
At first, the generalized problem is verified by creating a small sample from it. As for
an example three sets X1,X2 and X3 are chosen with k=3 non-negative integers. Let, the sets
be
X1={1,2,5}, X2 = {4,5,5} and X3={7,2,1}
Individual bounds of three sets are,
b(X1) = 8, b(X2) = 14 and b(X3) = 10.
Now, the clearly visible solution is S={1,2,4,5,5,7}.
Now, the bound of S b(S) = 24, which is less than the sum of individual bounds b(X1)+
b(X2)+ b(X3) = 32.
Now, extrapolating this problem to solve for n number of sets with each having k integers it
is needed to be formed graphs from the sets and edges of the graphs will denote the value of
each element (Borg 2015). Turing machine will then be used to formulate all combinations of
the n number of graphs to create each graph of n*k number of edges. Prim’s algorithm then
can be applied in repetition with some mathematical optimization software (like GRIN) to
find the minimum spanning tree for each graph (Wang and Hsieh 2018). The graph/s with the
minimum bound will be solution graph and then those can be converted to set from its edges
by applying simple algorithm. Furthermore, it is needed to increase the chosen bound by one
in each step until one unique solution of set is found.

4Solution of Non-deterministic Problem
Expected outcome:
It is expected that the their will be more than one satisfying subset S which will
satisfy the above conditions of using each element of the sets not more than once and the
solution set is of minimum bound. However, as the minimum chosen bound is increased the
solution sets will decrease but conditions may arise when increasing the bound in the next
step no solution can be found. The solution is expected to be checked within polynomial time
which is the function of number of sets and number of elements in each set (O(t)=f(n,k)).
Timeframe:
The total timeframe of the whole research can be subdivided in several parts which is
shown below.
Task name Time interval in days
Forming the NP problem 2 days
Analysing the problem as NP-hard or NP-
complete
1 day
Forming the algorithm to solve 2 days
Choosing appropriate Turing machine or
software
1 day
Obtaining guessed solutions 3 days
Checking the solutions 1 day
Finalizing the appropriate solution and any
further limitation to the solution
1 day
Total 11 days

5Solution of Non-deterministic Problem
Hence, the total research project is expected to be completed in approximately 11 days.
Furthermore, the obvious limitation of the project is that when increasing the number of sets
n or number of elements k, the number of graphs increases exponentially and the CPU time to
compute the guessed solutions through software increases. This introduces large time lapse
during computation and without sufficient memory the Turing machine can become
unresponsive. The best method to overcome this problem is to use multiple Turing machines
in a network which will reduce the computation time and system problems.

6Solution of Non-deterministic Problem
References:
Borg, P. (2015). A cross-intersection theorem for subsets of a set. Bulletin of the London
Mathematical Society, 47(2), 248-256.
Kearns, M., & Pitt, L. (2014, June). A polynomial-time algorithm for learning k-variable
pattern languages from examples. In Proceedings of the Second Annual ACM Workshop on
Computational Learning Theory (pp. 57-71).
Rendell, P., 2016. Turing Machine in Conway Game of Life. In Designing Beauty: The Art
of Cellular Automata (pp. 149-154). Springer, Cham.
Tang, H., Liu, X., Xiong, C., Wang, Z. and Ez Eldin, M.A.M., 2015. Proof of
nondeterministic polynomial-time complete problem for soil slope-stability evaluation.
International Journal of Geomechanics, 16(5), p.C4015004.
Traversa, F.L., Ramella, C., Bonani, F. and Di Ventra, M., 2015. Memcomputing NP-
complete problems in polynomial time using polynomial resources and collective states.
Science advances, 1(6), p.e1500031.
Wang, W.C. and Hsieh, M.C., 2018. Applying Prim’s Algorithm to Identify Isolated Areas
for Natural Disaster Prevention and Protection. Engineering, 10(07), p.417.