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. Learning-Based Abstractions for Nonlinear Constraint Solving We propose a new abstraction refinement procedure based on machine learning to improve the performan...
  2. Computational Materials Chemistry at the Nanoscale In order to illustrate how atomistic modeling is being used to determine the structure, physical, an...
  3. Seawater carboante chemistry and copper toxicity in the green tide alga Ulva prolifera in laboratory experiment Cu is considered to be toxic to macroalgae at higher levels. Ocean acidification can also alter the ...
  4. A microscopic mechanism of dielectric breakdown in SiO2 films: An insight from multi-scale modeling
  5. Identification of a vaccine candidate antigen, PfMAg-1, from Plasmodium falciparum with monoclonal antibody M26-32 Monoclonal antibody M26-32 has been shown to strongly inhibit the growth of Plasmodium falciparum in...

Otros recursos de la mismacolección

  1. Bimodal Logics with a “Weakly Connected” Component without the Finite Model Property There are two known general results on the finite model property (fmp) of commutators $[L_{0},L_{1}]...
  2. Infinite Computations with Random Oracles We consider the following problem for various infinite-time machines. If a real is computable relati...
  3. Why Intuitionistic Relevant Logic Cannot Be a Core Logic At the end of the 1980s, Tennant invented a logical system that he called “intuitionistic relevant l...
  4. Dunn–Priest Quotients of Many-Valued Structures J. Michael Dunn’s Theorem in 3-Valued Model Theory and Graham Priest’s Collapsing Lemma provide the ...
  5. Normal Numbers and Limit Computable Cantor Series Given any oracle, $A$ , we construct a basic sequence $Q$ , computable in the jump of $A$ , such tha...

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.