| RUS ENG |
| Full version |
|
|
|
| VIDEO LIBRARY |
|
Adian 90: Conference on Mathematical Logic, Algebra, and Computation
|
|||
|
|
|||
|
Complexity of structures P. E. Alaevab, V. L. Selivanovc a Sobolev Institute of Mathematics b Novosibirsk State University c Ershov Istitute of Informatics Systems SB RAS |
|||
|
Abstract: We consider notions and techniques needed for the development of the computable structure theory with bounded resourses. We are mainly interested in polynomial-time computable and primitive recursive structures. We analyze presentation complexity of some important concrete structures, in particular, number fields and finitely generated structures. We show that some problems in this area turns out to depend on complexity-theoretic conjectures like P=NP. Language: English |
|||