Immunity and simplicity for exact counting and other counting classes
J. Rothe (1999)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Displaying similar documents to “A survey on real structural complexity theory.”
Immunity and simplicity for exact counting and other counting classes
A non-deteministic time hierarchy over the reals.
F. Cucker, J. L. Montaña, L. M. Pardo (1993)
Extracta Mathematicae
Similarity:
Function operators spanning the arithmetical and the polynomial hierarchy
Armin Hemmerling (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
A modified version of the classical -operator as well as the first value operator and the operator of inverting unary functions, applied in combination with the composition of functions and starting from the primitive recursive functions, generate all arithmetically representable functions. Moreover, the nesting levels of these operators are closely related to the stratification of the arithmetical hierarchy. The same is shown for some further function operators known from computability...
Combined complexity classes for finite functions
Y. Breitbart, F. D. Lewis (1979)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
The intrinsic complexity of parametric elimination methods.
Heintz, J., Matera, G., Pardo, L.M., Wachenchauzer, R. (1998)
Electronic Journal of SADIO [electronic only]
Similarity:
Nonuniform complexity classes specified by lower and upper bounds
José L. Balcázar, Joaquim Gabarró (1989)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Complexity classes between and
J. Castro, C. Seara (1996)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
A note on separating the relativized polynomial time hierarchy by immune sets
Ker-I Ko (1990)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Self-reducibility structures and solutions of NP problems.
José L. Balcázar Navarro (1989)
Revista Matemática de la Universidad Complutense de Madrid
Similarity:
Using polynomial time self-reducibility structures, we characterize certain helping notions, show how the characterization provides the main tool for the proof of known relationships between decisional and functional NP-complete problems, and extend this relationships to the case of optimization NP-complete problems.