1) La descarga del recurso depende de la página de origen
2) Para poder descargar el recurso, es necesario ser usuario registrado en Universia


Opción 1: Descargar recurso

Detalles del recurso

Descripción

We study the notion of polynomial-time relation reducibility among computable equivalence relations. We identify some benchmark equivalence relations and show that the reducibility hierarchy has a rich structure. Specifically, we embed the partial order of all polynomial-time computable sets into the polynomial-time relation reducibility hierarchy between two benchmark equivalence relations $\mathsf{E}_{\lambda}$ and $\mathsf{id}$ . In addition, we consider equivalence relations with finitely many nontrivial equivalence classes and those whose equivalence classes are all finite.

Pertenece a

Project Euclid (Hosted at Cornell University Library)  

Autor(es)

Gao, Su -  Ziegler, Caleb - 

Id.: 69790185

Idioma: inglés  - 

Versión: 1.0

Estado: Final

Tipo:  application/pdf - 

Palabras clavepolynomial -  time relation reducibility - 

Tipo de recurso: Text  - 

Tipo de Interactividad: Expositivo

Nivel de Interactividad: muy bajo

Audiencia: Estudiante  -  Profesor  -  Autor  - 

Estructura: Atomic

Coste: no

Copyright: sí

: Copyright 2017 University of Notre Dame

Formatos:  application/pdf - 

Requerimientos técnicos:  Browser: Any - 

Relación: [References] 0029-4527
[References] 1939-0726

Fecha de contribución: 16-abr-2017

Contacto:

Localización:
* Notre Dame J. Formal Logic 58, no. 2 (2017), 271-285
* doi:10.1215/00294527-3867118

Otros recursos del mismo autor(es)

  1. Thermomechanical stress analysis of superplastic forming tool International audience
  2. Damages induced by thermomechanical cycles in superplastic forming tools 7th Asia-Pacific Symposiumon Engineering Plasticity and Its Applications (AEPA 2004), Shanghai Jiaot...
  3. Influence of Tasks Duration Variability on Task-Based Runtime Schedulers Research report on the Influence of Tasks Duration Variability on Task-Based Runtime Schedulers
  4. Inclusive search for a highly boosted Higgs boson decaying to a bottom quark-antiquark pair International audience
  5. Design of SPF dies based on advanced material behaviour models 8th International Conference on Superplasticity in Advanced Materials, St Catherines Coll, Oxford, E...

Otros recursos de la mismacolección

  1. Errata
  2. Invariance and Definability, with and without Equality The dual character of invariance under transformations and definability by some operations has been ...
  3. On the Jumps of the Degrees Below a Recursively Enumerable Degree We consider the set of jumps below a Turing degree, given by $\mathsf{JB}(\mathbf{a})=\{\mathbf{x}':...
  4. Negation-Free and Contradiction-Free Proof of the Steiner–Lehmus Theorem By rephrasing quantifier-free axioms as rules of derivation in sequent calculus, we show that the ge...
  5. Cardinality and Acceptable Abstraction It is widely thought that the acceptability of an abstraction principle is a feature of the cardinal...

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.