🚀 go-pugleaf

In <1ehq9hINN1e4@iskut.ucs.ubc.ca> unruh@physics.ubc.ca (William
Unruh) wrote:

> Could someone please remind us what P and NP mean? And what is being
> varied to get "polynomial time" -- ie what is polynomial in time , or
> what is time polynomial in?

In complexity theory, the time complexity of an algorithm is a
function t: N --> N such that t(n) = m if the algorithm uses at most m
steps on any input of length n. (In complexity theory "algorithm"
usually means "multi-tape semi-infinite-tape Turing machine".)

So "polynomial time" means that the time complexity is a polynomial in
n, n being the length of the input string. 

P is the class of problems that are solvable by a deterministic
algorithm whose time complexity is polynomial. 

NP is the class of problems that are solvable by a _nondeterministic_
algorithm whose time complexity is polynomial.

Since deterministic algorithms are special cases of nondeterministic
ones, clearly P is contained in NP. The question of whether P = NP
thus boils downs to determining whether or not nondeterminism is an
essential feature [as far as complexity is concerned]

- Hans

--
Hans H{\"u}ttel                          - hans@iesd.auc.dk  
Mathematics and Computer Science
Aalborg University, Fredrik Bajersvej 7E,
9220 Aalborg, DENMARK                     Ad slagne veje ?