Name: Simplicity, Relativizations and Nondeterminism
Creator: Balcázar Navarro, José Luis
Keywords: Complexity of computation (including implicit computational complexity), Computational, Simple sets, Analysis of algorithms and problem complexity, Complexity, 0102 computer and information sciences, 02 engineering and technology, Complexity classes, immunity, 01 natural sciences

Simplicity, relativizations and nondeterminism

descriptionPublicationkeyboard_double_arrow_right Article 01 Feb 1985 English Publisher:Society for Industrial & Applied Mathematics (SIAM)Journal:SIAM Journal on Computing, volume 14, pages 148-157 (issn: 0097-5397, eissn: 1095-7111,

Authors: Balcázar Navarro, José Luis;

doi: 10.1137/0214012

handle: 2117/102119

Simplicity, Relativizations and Nondeterminism

- Summary
- Subjects
- Metrics

Abstract

Relativizations of complexity classes in which simple sets exist are considered. A recursive oracle is constructed relative to which a simple set exists for NP. Some other general theorems are proven, showing that the time bounds are not a crucial hypothesis; bounds on the way in which the oracle is accessible, namely the number of queries and/or the number of nondeterministic steps, are shown to be the fundamental hypothesis. As a result, simple sets are shown to exist in many different relativized complexity classes Peer Reviewed

Related Organizations

Keywords

Complexity of computation (including implicit computational complexity), Computational, Simple sets, Analysis of algorithms and problem complexity, Complexity, Complexity classes, immunity, NP, complexity classes, Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat, :Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat [Àrees temàtiques de la UPC], Recursive oracle, Simplicity, recursive oracle, bounded queries, Relativizations, time bounds, Complexity, Computational, Nondeterminism, simple sets, Complexitat computacional

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	22
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%