Solution of Non-deterministic Problem

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.