Title :
A note on genericity and bi-immunity
Author :
Balcázar, José L. ; Mayordomo, Elvira
Author_Institution :
Dept. de Llenguatges i Sistemes Inf., Univ. Politecnica de Catalunya, Barcelona, Spain
Abstract :
Generic sets have all properties (from among a suitably chosen class) that can be enforced by finite extension arguments. In particular, p-generic sets known to be P-bi-immune. We try to clarify the precise relationship between genericity and bi-immunity by proposing an extended notion of bi-immunity that exactly characterizes the p-generic sets
Keywords :
computational complexity; set theory; bi-immunity; finite extension arguments; generic sets; genericity; p-generic sets; Computational modeling; Image segmentation; Measurement standards; Polynomials; Testing; Time measurement;
Conference_Titel :
Structure in Complexity Theory Conference, 1995., Proceedings of Tenth Annual IEEE
Conference_Location :
Minneapolis, MN
Print_ISBN :
0-8186-7052-5
DOI :
10.1109/SCT.1995.514857
