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


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)  


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


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

Otros recursos del mismo autor(es)

  1. Dark Matter Results from 225 Live Days of XENON100 Data 5 pages, 4 figures
  2. Comment on "On the subtleties of searching for dark matter with liquid xenon detectors" 3 pages, no figures
  3. The neutron background of the XENON100 dark matter experiment The XENON100 experiment, installed underground at the Laboratori Nazionali del Gran Sasso (LNGS), ai...
  4. Search for two-neutrino double electron capture of $^{124}$X with XENON100 International audience
  5. Search for new phenomena in dijet events using 37 fb−1 of pp collision data collected at s=13 TeV with the ATLAS detector Dijet events are studied in the proton-proton collision data set recorded at √ s = 13     TeV with...

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.