Menú

On Polynomial-Time Relation Reducibility

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 clave:  polynomial -  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. Application of isochronous mass spectrometry for the study of angular momentum population in projectile fragmentation reactions International audience
  2. Search for R-parity-violating supersymmetric particles in multi-jet final states produced in $p$-$p$ collisions at $\sqrt{s} =13$ TeV using the ATLAS detector at the LHC Results of a search for gluino pair production with subsequent R-parity-violating decays to quarks a...
  3. Search for a heavy Higgs boson decaying into a $Z$ boson and another heavy Higgs boson in the $\ell\ell bb$ final state in $pp$ collisions at $\sqrt{s}=13$ TeV with the ATLAS detector A search for a heavy neutral Higgs boson, $A$, decaying into a $Z$ boson and another heavy Higgs bos...
  4. Search for a new scalar resonance decaying to a pair of Z bosons in proton-proton collisions at $\sqrt{s} =$ 13 TeV A search for a new scalar resonance decaying to a pair of Z bosons is performed in the mass range fr...
  5. Observation of $\mathrm{t\overline{t}}$H production The observation of Higgs boson production in association with a top quark-antiquark pair is reported...

Otros recursos de la mismacolección

  1. Actualism, Serious Actualism, and Quantified Modal Logic This article studies seriously actualistic quantified modal logics. A key component of the language ...
  2. Ostrowski Numeration Systems, Addition, and Finite Automata We present an elementary three-pass algorithm for computing addition in Ostrowski numeration systems...
  3. Nonreduction of Relations in the Gromov Space to Polish Actions We show that in the Gromov space of isometry classes of pointed proper metric spaces, the equivalenc...
  4. A Problem in Pythagorean Arithmetic Problem 2 at the 56th International Mathematical Olympiad (2015) asks for all triples $(a,b,c)$ of p...
  5. Two More Characterizations of K-Triviality We give two new characterizations of $K$ -triviality. We show that if for all $Y$ such that $\Omega$...

Busca un recurso
Búsqueda avanzada
Colecciones destacadas
Recursos +solicitados

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.