The Complexity of the Disjunction and Existential Properties in Intuitionistic Logic
|
Descargar SCORM
Este recurso ha sido solicitado 1 veces (0 veces en los últimos 31 días).
Para poder solicitar este recurso debe identificarse como usuario de la biblioteca
|
| |
Ver
Detalles del recurso
|
|
|
The Complexity of the Disjunction and Existential Properties in Intuitionistic Logic
|
| Id. |
46918956 |
| Idioma |
inglés
|
| Titulo |
The Complexity of the Disjunction and Existential Properties in Intuitionistic Logic |
| Autor(es) |
Sam Buss
Grigori Mints
|
| Localización |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.1148
|
| Versión |
1.0 |
| Estado |
Final
|
| Descripción |
This paper considers the computational complexity of the disjunction and existential properties of intuitionistic logic. We prove that the disjunction property holds feasibly for intuitionistic propositional logic; i.e., from a proof of A B , a proof either of A or of B can be found in polynomial time. For intuitionistic predicate logic, we prove superexponential lower bounds for the disjunction property, namely, there is a superexponential lower bound on the time required, given a proof of A B , to produce one of A and B which is true. In addition, there is superexponential lower bound on the size of terms which fulfill the existential property of intuitionistic predicate logic.
|
| Tipo |
application/postscript
|
| Palabras clave |
intuitionistic logic
|
| Tipo de recurso |
Texto Narrativo
|
| Tipo de Interactividad |
Expositivo
|
| Nivel de Interactividad |
muy bajo
|
| Audiencia |
Estudiante
Profesor
Autor
|
| Estructura |
Atomic |
| Coste |
no
|
| Copyright |
sí
|
|
Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| Formatos |
application/postscript
|
| Requerimientos técnicos |
Browser: Any
|
| Relación |
[IsBasedOn] http://euclid.ucsd.edu/~sbuss/ResearchWeb/intuitionisticDP/paper.ps
[References] 10.1.1.101.4249
[References] 10.1.1.106.9717
|
| Fecha de contribución |
14-ago-2009 |
| Contacto |
|
|
|
|
|
Valoración de los usuarios
No hay ninguna valoración para este recurso. Sea el primero en
valorar este recurso.
|
|
|
|
