We systematise notions and techniques needed for development of the computable structure theory towards applications such as symbolic algorithms and on-line algorithms. On this way, we introduce some new notions and investigate their relation to the already existing ones. In particular, in the context of polynomial-time presentability such relation turns out to depend on complexity-theoretic conjectures like P = NP.
Original languageEnglish
Title of host publicationConnecting with Computability
Pages1-11
Number of pages11
DOIs
StatePublished - 1 Jan 2021
EventComputability in europe-2021 -
Duration: 5 Jul 2021 → …

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Nature
Volume12813
ISSN (Print)0302-9743

Conference

ConferenceComputability in europe-2021
Period5/07/21 → …

    Research areas

  • Computable presentation, Grzegorczyk’s presentation, Polynomial-time presentation, Quotient-structure, Structure

ID: 126985492