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 de la mismacolección

  1. Ekman’s Paradox Prawitz observed that Russell’s paradox in naive set theory yields a derivation of absurdity whose r...
  2. Forking and Dividing in Henson Graphs For $n\geq3$ , define $T_{n}$ to be the theory of the generic $K_{n}$ -free graph, where $K_{n}$ is ...
  3. Grades of Discrimination: Indiscernibility, Symmetry, and Relativity There are several relations which may fall short of genuine identity, but which behave like identity...
  4. New Degree Spectra of Abelian Groups We show that for every computable ordinal of the form $\beta=\delta+2n+1\gt 1$ , where $\delta$ is z...
  5. Prospects for a Naive Theory of Classes The naive theory of properties states that for every condition there is a property instantiated by e...

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.