Polynomial time uniformization and non-standard methods

被引：1

作者：

Ressayre, JP

机构：

[1] CNRS, Equuipe de Logique UA 753, Paris VII

来源：

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE | 1996年 / 16卷 / 1-4期

关键词：

D O I：

10.1007/BF02127795

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper presents the contents of a talk given in December 1990, during the second ''Journees sur les Arithmetiques Faibles'' held at the LITP, Paris; the talk was repeated during the 1991 Ecole de Printemps of Mejannes le Clap. The paper proves a polynomial time computability result for a class of NP inter co-NP problems, for which only the obvious exponential time algorithm was known. The result is proved by a striking use of non-standard methods, and it is not clear at all how to obtain it by standard methods.

引用

页码：75 / 88

页数：14