A proof that the set of NP-problems is bigger than the set of P-problems
by using a logical consideration
AKRAM LOUIZ
Informatics
Landshut Hochschule, Germany
Coopérative Essalam, Rue Kacem Amine, N°10, Settat
MOROCCO
Abstract: - The field of informatics is the domain that emerged by applying the mathematical logic on
electronic devices called computers in order to simplify many tasks for humans. The application of informatics
in all economic and scientific areas is the most important factor that made our civilization reach our current
phase of development. Nowadays, the experts and even the beginners of informatics are eager to use quantum
computers. However, there is still an unsolved problem of classical theoretical informatics in ordinary
electronic computers. It is the famous philosophical problem of the “Millenium Prize” of the Clay Mathematics
Institute concerning the complexity of problems that has been treated by many other researchers but without
acceptable sufficient answers. A solution to this problem can make all the fields based on informatics make
huge progress. And thus, thanks to my short studies about informatics, I present to you this mathematical proof
that deals with the sets of P problems, NP-Complete problems and NP-Hard problems in the field of classical
electronic computers in order to prove new formulas about the cardinals of each group of complexity problems
and about the intersections of each one of these sets. The aim is to contribute to an acceptable solution for this
Millenium Problem and the methodology is purely logical and mathematical. The readers won’t need any
complicated notions from the background of previous informatics or mathematics research in order to
understand the demonstrations of this article since the proof is based only on notions of sets by starting with
easy logical considerations. Furthermore, you will find in this work a proof of an interesting theorem about the
complexity of problems that allows us to identify NP-problems even if their algorithms have infinite time of
execution. This paper ends by proving that the set of NP-Problems is definitely bigger than the set of P-
Problems. Hence, all the readers are invited to understand and develop this work by inspecting the applied
logical considerations in order to succeed in finding a sufficient solution to the interesting Millenium Problem
of complexity.
Key-Words: - P problems ; NP problems ; NP-Complete problems ; NP-Hard problems ; complexity ;
cardinality ; set ; execution time; Clay Mathematics; Millenium problem.
Received: June 9, 2022. Revised: July 25, 2023. Accepted: September 8, 2023. Published: October 3, 2023.
1 Introduction
I've been motivated by my short studies about
informatics in order to produce a scientific article
that treats informatics with easy mathematical logic.
I've also been motivated by my previous work about
the Landau-Siegel Zeros [1] that may contribute to a
solution of the Millenium Prize of Riemann
Hypothesis. Hence, maybe this work can be
accepted as a contribution for the solution of the
important Millenium problem about the complexity
of problems.
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2023.22.19
Akram Louiz
E-ISSN: 2224-2872
159
Volume 22, 2023
This work concerns the cardinality and the
intersections of the P-problems, the NP problems
and the NP-Hard problems which are presented in
many works dealing with the notions of informatics
and logic [2,3,4]. However, we will focus in this
article on problems complexity by using the
ordinary notions available when we deal with
ordinary computers and not with nondeterministic
Turing machines (NTM) [5,6,7] or Quantum
Computers like it is explained in many works
[8,9,10].
Most of the results of this work are made by
considering that all NP-Hard problems that are not
NP-Complete problems have higher complexity
than NP-Complete problems and by considering that
all NP-Complete problems have one same
complexity that is directly linked to the value of a
number M that should exist and which is a fixed
number of P-Problems. We also supposed the
existence of a number of inputs that keeps all the P-
Problems with finite times of execution but makes
all NP-Hard problems with infinite times of
execution.
2 The considered modelling
Let's consider that each decidable problem can be
modelled by an algorithm that allows us to give an
estimation of the execution time of that algorithm.
The execution time of the algorithms of P problems
is finite. However, the execution times of NP-Hard
problems and NP-Complete problems are
considered infinite since these problems have never
been completely solved.
The set of P-problems is composed of elements
with and i>which are simple
problems that have a finite time of execution.
All the set of decidable problems respects a law
where And is a product that makes the sum
of the complexities of the problems of this product.
Consequently =pmeans that the execution
of the algorithm of the problem is equivalent to
the execution of the algorithm of the problem
followed by the execution of the algorithm of the
problem . Since the execution time of the
algorithm of the problem is finite, then is also
an element of the set of P-problems. Consequently,
an element of the set of P-problems can be a product
of n elements with n is a finite natural number.
Let's consider that there is an element e of the set of
P problems that has a null time of execution.
And thus:
=pe=p. (1)
And we don't care in this work about the presence of
a memory in the used computer. Hence, our
computer can repeat executing the same element
even if it is a solved problem.
And thus, we consider that we have:
=p
(2)
Hence, we consider that is in the set of P
problems for any element and for any strictly
positive natural number n since the problem
consists only on repeating the execution of the
same problem n finite times. Hence, our
computer shouldn't consider that is an infinite
loop when n is bigger than a defined value O that
depends on the computer system otherwise
becomes an undecidable problem.
We consider also that G is a fixed number of inputs
for all the decidable problems concerned by this
work. We know that the difference of complexity
time between P-problems and NP-Hard problems
increases as G becomes bigger. And thus, we
suppose the existence of a fixed number of inputs G
that keeps any P-problem as a product of a finite
number of elements which means that P-problems
will keep their finite times of execution, but we
consider that G is big enough to make all decidable
NP-Hard problems a product of an infinite number
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2023.22.19
Akram Louiz
E-ISSN: 2224-2872
160
Volume 22, 2023
of elements which means that the decidable NP-
Hard problems will have an infinite time of
execution. This means that even if the number G is
very big, it keeps the strict order of complexity time
for ordinary computers.
We consider that this supposition is possible in the
computing field and we use this fixed number G in
all the following demonstrations.
All decidable problems can be modelled by
algorithms, and we know that the execution time of
some algorithms can't end even if the algorithm
doesn't contain any infinite loop. We have no
solution to these problems and these problems can
belong to the sets of NP problems or NP-Hard
problems. There are indeed decision problems that
are decidable but in the set of NP-Hard problems
because of the time hierarchy theorem.
We will focus here on solving the optimization
corresponding to the decision problem (by using a
polynomial number of calls to the decision
problem).
We can accept that the algorithm execution that
doesn't end is equivalent to the execution of an
infinite series of simple problems . The NP-
Complete problems and the decidable NP-Hard
problems have never been solved even if they have
algorithms. And thus, the execution times of these
algorithms can be considered infinite.
Consequently, we consider that the set of NP-
Complete problems is composed of elements
with and j> with:
i= (3)
and we consider that in the set of NP-Hard problems
there are some elements: with
and k> with:
i= (4)
if is decidable.
However, we can check a solution for any NP-
problem in a finite execution time. Hence, let's
define an application Check that gives problems of
finite times of execution if it is possible when it is
applied to decidable problems. Since NP-problems
are all verifiable, then the application Check gives P
problems when it is applied to them.
In this article Check is an application:
from: Set of decidable problems to:
Set of P problems Set of NP-Hard problems
With: Check
i= with
and n finite (5)
And since is a solution of then we have also:
Check=p (6)
And also:
CheckCheckCheck=p
(7)
with:Check=e. (8)
However, since we don't know if NP = P or not, it is
still hard to say if we can verify a NP-Hard problem
in polynomial time or not. Hence, we don't check in
this work a solution for NP-Hard problems, and we
have to accept that :
Check=h with has an infinite time of
execution. (9)
We conclude that: Set of P problems
Check=p (10)
And:
Set of NP-Complete problems
Check
i= with and n finite
(11)
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2023.22.19
Akram Louiz
E-ISSN: 2224-2872
161
Volume 22, 2023
This useful result from the considerations will
allow us to develop a logical mathematical proof
about the sets of complexity.
The compilators of each programmation language
can propose programs that can count the number
of operations necessary for the execution of a
studied algorithm that is equivalent to a problem of
a given complexity.
3 A comparison between NP-
Complete problems and NP-Hard
problems
We remark that:
CheckCheck
i=
m= with and n finite (12)
Hence:
i=Check
i=n+
m= (13)
We have always:
i=
m= (14)
otherwise we would have:
Check
i=n+=e (15)
which is impossible since we have :
i=n+ for all elements . (16)
Let's consider that A is the inverse of
i= . (17)
Hence we have:
Check
i=n+
m= (18)
We also have:
i=n+n+i
i= (19)
Consequently:
m=A=Check n+i
i= (20)
We don't know if the decidable element n+i
i= is
verifiable (checkable) or not. Hence we consider
that A is an element of the set of NP-Hard
problems.
And we can change n in this method with n+l with l
is an integer with l>-n because if we have =p
then is also an element of the set of P
problems.
However, by using the new discovered element A,
we can discover many other elements of the set
of NP-Hard problems that have a bigger complexity
only by considering that =A where can be
any element of the set of decidable problems.
Finally we proved that each element of the set of
the NP-Complete problems produces many new
elements that have an algorithm with an infinite
time of execution and that we can't check easily
because we can't deduce obviously the algorithm of
the problem A from the algorithm of its inverse that
is in with the help of the application Check.
We conclude that each produces at least D
elements of the set of the NP-Hard problems with
D=cardSet of decidable problems.
And thus:
cardSet of NP-Hard problems
cardSet of decidable problems
cardSet of NP-Complete problems (21)
Let's remember that there exist many undecidable
problems in the set of NP-Hard problems such as
the Turing halting problem. For these kinds of
problems, there is no algorithm that can answer
correctly on all inputs.
4 The cardinal of NP-Complete
problems
If we make the product of all the elements of the
set of P problems, then we get a bigger problem B
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2023.22.19
Akram Louiz
E-ISSN: 2224-2872
162
Volume 22, 2023
that has an algorithm of an infinite time of execution
since the number of the elements of the set of P
problems can be considered infinite. However the
problem B is decidable since it can be modeled by
an algorithm that represents the product of problems
.
Thanks to the time hierarchy theorem, if we want to
reduce that complexity of the problem B then we
have to avoid executing some problems that belong
to the product of problems when we are
executing the algorithm of problem B.
If we want to remove an element from this
product (by multiplying B with the inverse of ) ,
then we have a number of possibilities equal to
cardSet of P problems. (22)
We consider that each possibility of this new
product is . If we want to remove an other element
from a product (by multiplying with the
inverse of ) , then we have another number of
possibilities equal to cardSet of P problems. This
is because the inverse of removes only the
element but not the element
where n can be
any positive natural number. Furthermore,
n+
always exists in the the product of problems that
makes B since n+1 is also finite.
We consider that each possibility of this new
product is ij.
We repeat the same operation L times with
cardSet of P problemsL=+ (23)
And this operation allows us to create a set DC of N
decidable elements with 0<k<N+ and each
i= is a problem that has an algorithm
with an infinite time of execution, and we have:
N=cardSet of P problems (24)
L can even have an infinite value but in order to
have: Set of NP-Hard problems
Set of decidable problems (25)
We should always have:
cardSet of P problemsL=+ (26)
We know that when L increases, the complexity of
the problems decreases, and thus we can find the
smallest value M that reduces the complexity of all
the problems when L=M such as we get:
Set of NP-Complete problems . (27)
This means that with L=M we have
Set of NP-Complete problems DC. (28)
Consideration:
Despite its high complexity, each NP-Complete
problem can be reduced to another NP-Complete
problem and vice versa since NP-Complete
problems are also NP problems. Hence, let's
consider that all NP-Complete problems have the
same complexity time that is directly linked to the
value of M. We consider that if the value of L
decreases then all the elements of the set DC
become NP-Hard problems. This is because we
consider that all NP-Hard problems that are not NP-
Complete problems have higher complexity than
NP-Complete problems.
This means that with L=M we have
Set of NP-Complete problems=DC . (29)
In this case, we have:
cardSet of NP-Complete problems
cardSet of P problems (30)
This result is an equation that allows us also to
understand the difference between the cardinals of
the set of NP-Complete problems and the set of P-
problems even if these two sets have both infinite
cardinals.
5 The bijection that links P problems
and the set of decidable problems
Let's consider that PW is the power set of the set of
P problems with the decidable problem e removed.
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2023.22.19
Akram Louiz
E-ISSN: 2224-2872
163
Volume 22, 2023
Let's consider that PW with i> are the sets that
are elements of PW except the element: (the
empty set) that we won't use.
Let's consider an application G defined:
from the set PW to Set of decidable problems
with: PW equals the product of all the elements
of PW.
Since the elements PW are all the possible subsets
of the set of P problems, then the elements PW
are all the possible elements of the set of decidable
problems with the decidable problem e removed.
Hence, the application G is a bijection between:
PW
and the set of decidable problems considered
without the element e.
And thus:
cardSet of decidable problems
cardSet of P problems (31)
Consequently:
cardSet of decidable problems
cardSet of P problems (32)
We can deduce that:
cardSet of P problemscardSet of P problems
(33)
And: cardSet of NP problems
cardSet of P problems
(34)
And also:
cardSet of NP-Complete problems
cardSet of P problems (35)
This result is a new attempt to compare the
cardinals of the set of NP-Complete problems and
the set of P-problems even if these two sets have
both infinite cardinals.
6 First conclusions and remarks
We can deduce from formula (21) and formula (31)
that:
cardSet of NP-Hard problems
cardSet of P problems
cardSet of NP-Complete problems (36)
And thus, we can deduce from formula (35) and
formula (36) that:
cardSet of NP-Complete problems
cardSet of NP-Hard problems
cardSet of NP-Complete problems (37)
Which is equivalent to:
cardSet of NP-Complete problems
cardSet of NP-Hard problems (38)
And we can also conclude from formula (30) and
formula (35) that:
cardSet of P problems
cardSet of P problems (39)
where M is the smallest value that reduces the
complexity of the elements of the Set DC into the
complexity of NP-Complete problems. However,
we should always have cardSet of P problems
M=+.
Furthermore, the value of
cardSet of P problems increases when M
increases.
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2023.22.19
Akram Louiz
E-ISSN: 2224-2872
164
Volume 22, 2023
After this step, we have new formulae that allow us
to develop logical mathematical demonstrations
about the sets of complexity especially by using
their cardinals.
7 Investigating the value of M that
reduces the complexity of the elements
of the Set DC into the complexity of
NP-Complete problems
Now we should compare :
cardSet of P problems
and: cardSet of P problems cardSet of P problems
Let's consider that:
M= cardSet of P problems
with x>1. (40)
Hence, we have:
cardSet of P problems
cardSet of P problemscardSet of P problems
(41)
And thus:
cardSet of P problems
cardSet of P problems
cardSet of P problems (42)
However cardSet of P problems
is infinite
for any finite positive number x.
We conclude that if M= cardSet of P problems
with x>1,
then we have: cardSet of P problems is much
bigger than cardSet of P problems.
Consequently, we should have:
M< cardSet of P problems
x>1 and x finite (43)
This easy mathematical result characterizes the
point M. However, other characteristics can be
deduced about the point M in order to develop easy
other demonstrations about the sets of complexity.
8 Second conclusions and remarks
If we make the set DC by using M with:
cardSet of P problemsM=+
but cardSet of P problems
with x is a real positive finite number, then we have:
cardSet of P problems
cardSet of P problems
which makes a contradiction.
And thus, we have always: M< cardSet of P problems
x>1 and x finite .
We remark that when a decidable problem is
expressed as:
i= (44)
where H is a natural number that respects
H=cardSet of P problemsN'=+ (45)
with: N' cardSet of P problems
>M with x is a
finite real number with x>1 (46)
Then we have:
cardSet of P problems
(47)
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2023.22.19
Akram Louiz
E-ISSN: 2224-2872
165
Volume 22, 2023
we can also have x bigger that 1 but very close to 1
and consider that x=+, and this can be useful as
demonstrated in the final results of this article since
it still allows that:
cardSet of P problems
.
Furthermore, the problem: stays a decidable
problem because the number H exists and we can
also have H=+. However we should also remark
from the previous paragraphs that in this case
has a complexity of NP-Problems since N>M.
Theorem:
When a decidable problem is expressed as:
i= where are P problems that have a
finite time of execution
If we have cardSet of P problems
where x is a finite real number with x>1
then the problem is a NP-Problem.
Remark: This new theorem about NP-Complete
problems doesn’t require that . This
theorem can be very useful for the readers who
aim to make personal demonstrations about the
sets of complexity or to propose a personal solution
for the Millenium Problem of Clay Mathematics
about complexity problems (P=NP ?).
An artificial intelligence can also be useful to
compare and verify any proposed demonstrations
to this problem based on principles of informatics
theory.
9 Investigation about NP-Problems
NB: This part of the article is a personal attempt
to easily finish the demonstration concerning the
millennium problem P=NP. This part of the
demonstration needs that the existence of the two
considered numbers “z” and “ n’ ” be logically
possible in the field of computer science by
taking in consideration the mathematical logics
respected in this article.
Let's consider a decidable problem expressed as
i= (48)
where are P problems that have a finite time of
execution with:
cardSet of P problems
where
z>1. (49)
The problem is a NP-Problem. Consequently,
let's find the cardinal of the set DH of all the
possibilities of the problems HJsimilar to .
Since cardSet of P problems
for
each HJ
i=in DH, then we consider that H
is the integer part of cardSet of P problems
.
Consequently, we write:
H= cardSet of P problems
(50)
Hence, the number of possibilities of HJcan be
expressed as:
D=cardSet of P problemscardSet of P problems
(51)
And thus:
cardDH
cardSet of P problemscardSet of P problems
cardSet of P problems
J=
(52)
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2023.22.19
Akram Louiz
E-ISSN: 2224-2872
166
Volume 22, 2023
We remark that: cardDH
cardSet of P problems (53)
However, we defined the Set DH as a set that
respects: DH Set of NP-problems (54)
Which means that:
cardDH<cardSet of NP-problems (55)
Which is equivalent to:
cardSet of NP-problems
cardSet of P problemscardSet of P problems
cardSet of P problems
J=
(56)
And we conclude that:
cardSet of P problems<cardSet of NP-problems
(57)
Which means that:
NP (58)
However, since we have:
cardSet of NP problemscardSet of P problems
Then we have in this case:
cardSet of P problemscardSet of P problems
cardSet of P problems
J=
cardSet of P problems
(59)
And thus we should check if this is a contradiction
for any real number z with z>1.
Let's consider that z= cardSet of P problems
cardSet of P problemsn' where n'
has a natural positive value. (60)
In this case, even if cardSet of P problems can be
considered infinite, we should find a big natural
number n' in order to have at least z=+ . (61)
and we have : cardSet of P problems
J=n' (62)
And we have: cardSet of P problems
=n' (63)
Hence, if z= cardSet of P problems
cardSet of P problemsn' then:
cardSet of P problemscardSet of P problems
cardSet of P problems
J=
card
n'
i=Set of P problemsn' (64)
And if n' allows also to respect the scale of limits
then we have:
cardSet of P problems>cardSet of NP problemsn'+>n'
cardSet of NP problemsn' card
n'
i=Set of P problemsn'
(65)
And thus, if z= cardSet of P problems
cardSet of P problemsn' where n' exists,
then this formula stays correct:
cardSet of P problemscardSet of P problems
cardSet of P problems
J=
cardSet of P problems (66)
However we should choose the appropriate number
n' that is big enough to be significant compared to
cardSet of P problems in order to verify the
formula (61) and the formula (66) at the same time.
We conclude that if we find the appropriate real
number z that prevents formula (66) from being a
contradiction, then we can accept this conclusion:
Final conclusion depending on the taken
considerations:
We have:
cardSet of P problems<cardSet of NP-problems
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2023.22.19
Akram Louiz
E-ISSN: 2224-2872
167
Volume 22, 2023
And thus: NP.
10 Conclusion
The results of this work are made by considering
that:
1) A fixed number of inputs G exists and can be
defined in the field of computing such as G keeps
any P-problem as a product of a finite number of
P-problems , but G is big enough to make all
decidable NP-Hard problems a product of an
infinite number of elements .
2) All NP-Hard problems that are not NP-
Complete problems have higher complexity than
NP-Complete problems and by considering that
all NP-Complete problems have one same
complexity that is directly linked to the value of a
number M that should exist and which is a fixed
number of P-Problems. M should have a natural
value that respects: M< cardSet of P problems
x>1 and x finite.
3) The appropriate real number z that prevents
formula (66) from being a contradiction exists
and can be defined in the computing field.
We proved in this article by using these
considerations that:
cardSet of NP-Hard problems
cardSet of decidable problems
cardSet of NP-Complete problems
And also: cardSet of NP-Complete problems
cardSet of P problems
where M is the smallest value that reduces the
complexity of the elements of the Set DC presented
above into the complexity of NP-Complete
problems.
However, we should always have
cardSet of P problemsM=+.
We proved also that:
cardSet of decidable problems
cardSet of P problems
Hence, we deduced that: cardSet of P problems
cardSet of P problems
And: cardSet of NP problems
cardSet of P problems
And also: cardSet of NP-Complete problems
cardSet of P problems
We concluded that:
cardSet of NP-Hard problems
cardSet of P problems
cardSet of NP-Complete problems
And that: cardSet of NP-Complete problems
cardSet of NP-Hard problems
cardSet of NP-Complete problems
Which is equivalent to:
cardSet of NP-Complete problems
cardSet of NP-Hard problems
We could also conclude that:
cardSet of P problems
cardSet of P problems
with always M< cardSet of P problems
x>0 and x finite
And we proved that:
cardSet of NP-problems
cardSet of P problemscardSet of P problems
cardSet of P problems
J=
Finally we concluded this theorem:
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2023.22.19
Akram Louiz
E-ISSN: 2224-2872
168
Volume 22, 2023
When a decidable problem is expressed as:
i= where are P problems that have a
finite time of execution
If x is a finite real number with x>1, then we have:
x is a finite real number with x>1 and
cardSet of P problems
is a NP-Problem
And if we can define in the field of computer
science the considered number “z” that prevents
the following formula from being a contradiction:
cardSet of P problemscardSet of P problems
cardSet of P problems
J= cardSet of P problems
then this allows to make this conclusion:
We have:
cardSet of P problems<cardSet of NP-problems
And thus: NP.
NB: the value of the number “M” can be studied
further in order to find new mathematical
characteristics that allow finding a solution to the
problems of complexity sets without needing to
find the considered numbers “z” and “ n’ ”.
Final conclusion:
The Millenium problem (P=NP ?) is not only a
problem of informatics but also a logical
philosophical problem. A solution to this Clay
Mathematics problem will allow us to classify
logical problems better in order to find the suitable
computer for each kind of problems which will
allow us to enhance the efficiency of all the fields
that need informatics.
This proof can also be useful as a basis for the
researchers who deal with Quantum Computers.
Furthermore, the value of the demonstrated
number “M” can be studied further in order to
find a solution to this Millenium problem without
needing to find the considered number “z”.
The readers are invited to this opportunity in order
to investigate the proposed logical considerations
for a solution to this important Clay Mathematics
Millenium problem.
References:
[1] akram louiz. Complex mathematical
statements useful as criterion for Landau-
Siegel Zeros, 29 January 2023, PREPRINT
(Version 2) available at Research Square.
DOI: https://doi.org/10.21203/rs.3.rs-
2520944/v2
[2] Hidalgo-Herrero, M., Rabanal, P.,
Rodriguez, I., & Rubio, F. (2013).
Comparing problem solving strategies for
NP-hard optimization problems.
Fundamenta Informaticae, 124(1-2), 1-25,
2013, DOI: https://doi.org/10.3233/FI-
2013-822
[3] Izadkhah, H. (2022). P, NP, NP-Complete,
and NP-Hard Problems. In Problems on
Algorithms: A Comprehensive Exercise
Book for Students in Software
Engineering (pp. 497-511). Cham: Springer
International Publishing, 2022. DOI:
https://doi.org/10.1007/978-3-031-17043-
0_15
[4] Alizadeh, R., Allen, J.K. & Mistree, F.
Managing computational complexity using
surrogate models: a critical review. Res Eng
Design 31, 275–298, 2020. DOI:
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2023.22.19
Akram Louiz
E-ISSN: 2224-2872
169
Volume 22, 2023
https://doi.org/10.1007/s00163-020-00336-
7
[5] Savitch, W. J. (1970). Relationships
between nondeterministic and deterministic
tape complexities. Journal of computer and
system sciences, 4(2), 177-192, 1970. DOI:
https://doi.org/10.1016/S0022-
0000(70)80006-X
[6] Paul, W. J., Pippenger, N., Szemeredi, E.,
& Trotter, W. T. (1983, November). On
determinism versus non-determinism and
related problems. In 24th Annual
Symposium on Foundations of Computer
Science (sfcs 1983) (pp. 429-438). IEEE,
1983. DOI:
https://doi.org/10.1109/SFCS.1983.39
[7] ZAK, S. (1983). A turing machine time
hierarchy. Theoretical computer
science, 26(3), 327-333, 1983. DOI:
https://doi.org/10.1016/0304-
3975(83)90015-4
[8] Freedman, M. H. (1998). P/NP, and the
quantum field computer. Proceedings of the
National Academy of Sciences, 95(1), 98-
101, 1998. DOI:
https://doi.org/10.1073/pnas.95.1.98
[9] Gharibian, S., Huang, Y., Landau, Z., &
Shin, S. W. (2015). Quantum hamiltonian
complexity. Foundations and Trends® in
Theoretical Computer Science, 10(3), 159-
282, 2015. DOI:
https://doi.org/10.1561/0400000066
[10] Ohya, M., & Masuda, N. (2000).
NP problem in quantum algorithm. Open
Systems & Information Dynamics, 7(1), 33-
39, 2000. DOI:
https://doi.org/10.1023/A:1009651417615
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2023.22.19
Akram Louiz
E-ISSN: 2224-2872
170
Volume 22, 2023
Contribution of Individual Authors to the
Creation of a Scientific Article (Ghostwriting
Policy)
The author contributed in the present research, at all
stages from the formulation of the problem to the
final findings and solution.
Sources of Funding for Research Presented in a
Scientific Article or Scientific Article Itself
No funding was received for conducting this study.
Conflict of Interest
The author has no conflict of interest to declare that
is relevant to the content of this article.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en
_US
