The P-NP Question and Recent Independence Results
Loading...
Authors
Philips, N.C.K.
Issue Date
1979
Type
Article
Language
en
Keywords
Alternative Title
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
Description
Citation
Philips, N.C.K. (1979) The P-NP Question and Recent Independence Results. Quaestiones Informaticae, Vol 1 no 1, 1979
Publisher
Computer Society of South Africa (on behalf of SAICSIT)
License
Journal
Volume
Issue
PubMed ID
DOI
ISSN
0254-2757