The P-NP Question and Recent Independence Results

dc.contributor.author	Philips, N.C.K.
dc.date.accessioned	2018-05-21T14:20:16Z
dc.date.available	2018-05-21T14:20:16Z
dc.date.issued	1979
dc.identifier.citation	Philips, N.C.K. (1979) The P-NP Question and Recent Independence Results. Quaestiones Informaticae, Vol 1 no 1, 1979	en
dc.identifier.issn	0254-2757
dc.identifier.uri	http://hdl.handle.net/10500/23974
dc.description.abstract	Despite intensive research the P = NP question is unresolved and the research suggests thatitis hard to answer. The corresponding question for query machines with recursive oracles is undecidable in set theory. Simply determining whether a procedure halts or the running time of an algorithm may be harder than we expect. There is a Turing machine which does not halt yet its halting is undecidable in set theory. There is an algorithm which runs in time n2 yet it cannot be proved in set theory to run in any time less than 2". 26	en
dc.language.iso	en	en
dc.publisher	Computer Society of South Africa (on behalf of SAICSIT)	en
dc.title	The P-NP Question and Recent Independence Results	en
dc.type	Article	en
dc.description.department	School of Computing	en