Complexity Issues for Preorders on Finite Labeled Forests

DOI10.1007/978-3-642-21875-0_12zbMath1344.68096OpenAlexW1571189667MaRDI QIDQ3091446

Victor L. Selivanov, Peter H. Hertling

Publication date: 9 September 2011

Published in: Models of Computation in Context (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-21875-0_12

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computation over the reals, computable analysis (03D78)

Related Items (2)

The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma ⋮ On the main scientific achievements of Victor Selivanov

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the homomorphism order of labeled posets
• NP-partitions over posets with an application to reducing the set of solutions of NP problems
• Labeled posets are universal
• Weihrauch degrees, omniscience principles and weak computability
• Effective Choice and Boundedness Principles in Computable Analysis
• A Gandy Theorem for Abstract Structures and Applications to First-Order Definability
• Undecidability in Weihrauch Degrees
• Hierarchies of Δ⁰₂‐measurable k ‐partitions
• Undecidability in the Homomorphic Quasiorder of Finite Labelled Forests
• Logical Approaches to Computational Barriers

This page was built for publication: Complexity Issues for Preorders on Finite Labeled Forests