This paper discusses the scope and goals of structural complexity theory, describes some working hypotheses of this field and summarizes (some) recent developments.
Computational complexity theory is the study of the quantitative laws that govern computing. A central topic in this study is the classification of computational problems by the amount of various ...computational resources required for their solution and, particularly, to find the limits of feasible computation. Computational complexity has discovered (or defined) a beautiful structure of natural, mathematically robust complexity classes that give an intuitively satisfying classification of the feasibly and near-feasibly computable problems. These complexity classes are defined by the bounds on computational resources or by the natural complete problems to which other problems in the class can be easily reduced. They can also be defined very naturally, in a noncomputational way, by the expressive power of various logical formalisms, emphasizing that they are natural, robust and important mathematical objects. Notwithstanding considerable effort over several decades, there are no proofs that all these classes are indeed different. The resolution of the separation questions for these complexity classes can be considered one of the most important set of open problems in theoretical computer science.
The Database and Expert Systems Applications (DEXA) conferences bring together researchers and practitioners from all over the world to exchange ideas, experiences and opinions in a friendly and ...stimulating environment. The papers are at once a record of what has been achieved and the first steps towards shaping the future of information systems. DEXA covers a broad field, and all aspects of database, knowledge base and related technologies and their applications are represented. Once again there were a good number of submissions: 241 papers were submitted and of these the programme committee selected 103 to be presented. DEXA’99 took place in Florence and was the tenth conference in the series, following events in Vienna, Berlin, Valencia, Prague, Athens, London, Zurich, Toulouse and Vienna. The decade has seen many developments in the areas covered by DEXA, developments in which DEXA has played its part. I would like to express thanks to all the institutions which have actively supported and made possible this conference, namely: • University of Florence, Italy • IDG CNR, Italy • FAW – University of Linz, Austria • Austrian Computer Society • DEXA Association In addition, we must thank all the people who have contributed their time and effort to make the conference possible. Special thanks go to Maria Schweikert (Technical University of Vienna), M. Neubauer and G. Wagner (FAW, University of Linz). We must also thank all the members of the programme committee, whose careful reviews are important to the quality of the conference.
In this note we discuss the similarities and differences between Gödel's result about non-recursive shortening of proofs of formal systems by additional axioms and the corresponding results about the ...succinctness of different representations of languages.
In this paper we study the computational complexity of sets of different densities in NP. We show that the deterministic computation time for sets in NP can depend on their density if and only if ...there is a collapse or partial collapse of the corresponding higher nondeterministic and deterministic time bounded complexity classes. We show also that for NP sets of different densities there exist complete sets of the corresponding density under polynomial time Turing reductions. Finally, we show that these results can be interpreted as results about the complexity of theorem proving and proof presentation in axiomatized mathematical systems. This interpretation relates fundamental questions about the complexity of our intellectual tools to basic structural problems about P, NP, CoNP and
Pspace, discussed in this paper.
The purposes of this paper is to give simple new proofs of some interesting recent results about the relative succinctness of different representations of regular, deterministic and unambiguous ...context-free languages and to derive some new results about how the relative succinctness of representations change when the representations contain a formal proof that the languages generated are in the desired subclass of languages.
Innovation and Obstacles: the Future of Computing Clark, D.D.; Feigenbaum, E.A.; Hartmanis, J. ...
Computer (Long Beach, Calif.),
1998-Jan., 1998-01-00, 19980101, Letnik:
31, Številka:
1
Journal Article
Recenzirano
Odprti dostop
In this multidisciplinary glimpse forward, some of this decade's key players offer opinions on a range of topics--from what has driven progress, to where innovation will come from and to obstacles we ...have yet to overcome.
Creative sets or the complete recursively enumerable sets play an important role in logic and mathematics and they are known to be recursively isomorphic. Therefore, on the one hand, all the complete ...sets can be viewed as equivalent, on the other hand, we intuitively perceive some complete sets as more ‘natural and simpler’ than others. In this note we try to capture this intuitive concept precisely by defining a complete set to be natural if all other recursively enumerable sets can be reduced to it by computationally simple reductions and show that these natural complete sets are all isomorphic under the same type of computationally simple mappings. The same ideas are applied to define natural Gödel numberings and, using natural Gödel numberings, to show that natural creative sets coincide with the natural complete sets.
PDF
