English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Recently, several authors have explored the connections between NP-complete problems for finite objects and the complexity of their analogs for infinite objects. In this paper, we will categorize infinite versions of several problems arising from finite complexity theory in terms of their recursion theoretic complexity and proof theoretic strength. These infinite analogs can behave in a variety of unexpected ways. Startling parallels exist between the computational complexity of certain graph theoretic problems and the recursion theoretic complexity and proof theoretic strength of their infi- nite analogs. For example, the problem of deciding which finite graphs have an Euler path is known to be P-time computable (9), and Beigel and Gasarch (4) have shown that the problem of deciding which infinite recursive graphs have an Euler path is arithmetical. By contrast, the problem of deciding which finite graphs have Hamilton paths is NP-complete (8), and Harel (6) has shown that the problem of deciding which infinite recursive graphs have a Hamilton graph is  1 complete. Thus, the possibly greater computational complex- ity is paralleled by a demonstrable increase in recursion theoretic complexity. This pattern can also be seen through an application of the techniques of reverse mathematics. The

Infinite Versions of Some Problems from Finite Complexity Theory