P versus UP
(P versus UP)
Frank Vega (vega.frank@gmail.com)
Datys
This paper appears in: Revista IEEE América Latina
Publication Date: June 2012
Volume: 10, Issue: 4
ISSN: 15480992
Abstract:
The existence of oneway functions is a question that has not yet been answered. If we solve the problem P versus UP showing that both classes are different, then it would result in fact there are strong oneway functions and thus P is not equal to NP. In this work we showed that some kinds of unambiguous Turing machines can not be converted into deterministic, because it will imply that some Turing machines which do not halt for some inputs could be decided in polynomial time by certain deterministic Turing machines. But, is impossible that we can decide in polynomial time over a deterministic Turing machine if any deterministic Turing machine does not halt in polynomial time. Therefore by the rule of reduction ad absurdum we have that P and UP are different.
Index Terms:
Complexity classes,Turing machines,Oneway functions
Documents that cite this
document
This function is not implemented yet.
[PDF FullText (259)]
