A hierarchy that does not collapse : alternations in low level space
Page 1
Displaying 1 – 14 of 14
A new algorithm for recognizing the unknot.
Birman, Joan S., Hirsch, Michael D. (1998)
Geometry & Topology
A new decidable Horn fragment of predicate calculus.
Orevkov, V.P. (2004)
Zapiski Nauchnykh Seminarov POMI
A non-deteministic time hierarchy over the reals.
F. Cucker, J. L. Montaña, L. M. Pardo (1993)
Extracta Mathematicae
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
A note on the asymptotic and computational complexity of graph distinguishability.
Russell, Alexander, Sundaram, Ravi (1998)
The Electronic Journal of Combinatorics [electronic only]
A survey on real structural complexity theory.
Meer, Klaus, Michaux, Christian (1997)
Bulletin of the Belgian Mathematical Society - Simon Stevin
Algebraic complexity theory. I: An introduction. (Algebraische Komplexitätstheorie. I: Eine Einführung.)
Bürgisser, Peter, Clausen, Michael (1996)
Séminaire Lotharingien de Combinatoire [electronic only]
Algebraic complexity theory. II: Tast matrix multiplication and combinatorics. (Algebraische Komplexitätstheorie. II: Schnelle Matrixmultiplikation und Kombinatorik.)
Bürgisser, Peter (1996)
Séminaire Lotharingien de Combinatoire [electronic only]
Algebraic complexity theory. III: On the complexity of the computation of permanents. (Algebraische Komplexitätstheorie. III: Zur Berechnungskomplexität von Permanenten.)
Clausen, Michael (1996)
Séminaire Lotharingien de Combinatoire [electronic only]
Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation
Marc Demange, Vangelis Paschos (2002)
RAIRO - Operations Research - Recherche Opérationnelle
The main objective of the polynomial approximation is the development of polynomial time algorithms for NP-hard problems, these algorithms guaranteeing feasible solutions lying “as near as possible” to the optimal ones. This work is the fist part of a couple of papers where we introduce the key-concepts of the polynomial approximation and present the main lines of a new formalism. Our purposes are, on the one hand, to present this theory and its objectives and, on the other hand, to discuss the...
Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : de la structure de NPO à la structure des instances
Marc Demange, Vangelis Paschos (2002)
RAIRO - Operations Research - Recherche Opérationnelle
Cet article est la suite de l’article «Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation» où nous avons présenté et discuté, dans le cadre d’un nouveau formalisme pour l’approximation polynomiale (algorithmique polynomiale à garanties de performances pour des problèmes NP-difficiles), des outils permettant d’évaluer, dans l’absolu, les proporiétés d’approximation de problèmes difficiles. Afin de répondre pleinement à l’objectif...
Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
Marc Demange, Vangelis Paschos (2010)
RAIRO - Operations Research
This paper is the continuation of the paper “Autour de nouvelles notions pour l'analyse des algorithmes d'approximation: Formalisme unifié et classes d'approximation” where a new formalism for polynomial approximation and its basic tools allowing an “absolute” (individual) evaluation the approximability properties of NP-hard problems have been presented and discussed. In order to be used for exhibiting a structure for the class NPO (the optimization problems of NP), these tools must be enriched...
Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
Marc Demange, Vangelis Paschos (2010)
RAIRO - Operations Research
Cet article est le premier d'une série de deux articles où nous présentons les principales caractéristiques d'un nouveau formalisme pour l'approximation polynomiale (algorithmique polynomiale à garanties de performances pour les problèmes NP-difficiles). Ce travail est l'occasion d'un regard critique sur ce domaine et de discussions sur la pertinence des notions usuelles. Il est aussi l'occasion de se familiariser avec l'approximation polynomiale, de comprendre ses enjeux et ses méthodes. Ces deux...
Currently displaying 1 – 14 of 14
Page 1